Discrete : wip-worktree-statedescrete

1 files changed, 69 insertions, 0 deletions

diff --git a/01-knapsack/ks_dp-ng.c b/01-knapsack/ks_dp-ng.c
index 7830651..282cecf 100644
--- a/01-knapsack/ks_dp-ng.c
+++ b/01-knapsack/ks_dp-ng.c
@@ -160,6 +160,75 @@ static void solve(Solver* solver)
      printf("loops count: %u\n", counter);
 }
 
+static void reset_output(char *output, int bits)
+{
+   char *ch;
+   char *end;
+
+   end = output + bits;
+   for (ch = output; ch < end; )
+     {
+        (*ch++) = '0';
+        (*ch++) = ' ';
+     }
+   ch--;
+   *ch = '\0';
+}
+
+static int print(Solver* solver)
+{
+   int ret;
+   int v, w;
+   char *output;
+   const Item *item;
+   const SolverData *data;
+
+   output = calloc((solver->n * 2), sizeof(char));
+   if (!output)
+     {
+        fprintf(stderr, "ERROR: output calloc\n");
+        return EXIT_FAILURE;
+     }
+   reset_output(output, (solver->n * 2));
+
+   data = solver->column + solver->k;
+   printf("%d %d\n", data->v, 0);
+
+   v = 0;
+   w = 0;
+   /* for (data = solver->column + solver->k; data->i != -1 ; data -= item->w) */
+   for (data = solver->column + solver->k; data->s != -1 ; data -= item->w)
+     {
+        /* item = &solver->items[data->i]; */
+        item = &solver->items[data->s];
+        output[(item->i) * 2] = '1';
+        if (debug > 1)
+          printf("  from % 6d  - take % 4d (% 4d % 4d)\n",
+                 data->v, item->i, item->v, item->w);
+        v += item->v;
+        w += item->w;
+     }
+   printf("%s\n", output);
+
+   free(output);
+
+   ret = EXIT_SUCCESS;
+   data = solver->column + solver->k;
+   if (v != data->v)
+     {
+        fprintf(stderr, "ERROR: value %d != %d\n", v, data->v);
+        ret = EXIT_FAILURE;
+     }
+   if (w > solver->k)
+     {
+        fprintf(stderr, "ERROR: weight %d > %d\n", w, solver->k);
+        ret = EXIT_FAILURE;
+     }
+
+   return ret;
+
+}
+
 static int check(Solver *solver, int excpected_value)
 {
    const SolverItem *data;