Discrete : 01-knapsack: optimize memory mgmt for items

1 files changed, 31 insertions, 34 deletions

diff --git a/01-knapsack/ks_dp.c b/01-knapsack/ks_dp.c
index 1ba27b9..6ed8d00 100644
--- a/01-knapsack/ks_dp.c
+++ b/01-knapsack/ks_dp.c
@@ -21,6 +21,12 @@ static inline int get_bit(word_t *bits, int b)
    return ((bits[bindex(b)] & (1 << (boffset(b)))) >> (boffset(b)));
 }
 
+typedef struct _Item
+{
+   int value;
+   int weight;
+} Item;
+
 typedef struct _SolverData {
      int v;
      word_t *bits;
@@ -30,10 +36,9 @@ typedef struct _Solver
 {
    int k;               // capacity
    int n;               // items #
-   int *values;         // item values
-   int *weights;        // item weights
    int nw;              // # bytes per bits array
    size_t sd_sz;        // solver data size
+   Item *items;         // items
    SolverData *data;    // solver data
 } Solver;
 
@@ -41,26 +46,25 @@ static void solve(Solver* solver)
 {
    int n, k, nw;
    size_t sd_sz;
-   int *values, *weights;
 
    int i, j;
    int v, w;
    char *data_base;
+   Item *item;
    SolverData *c, *p;
 
    sd_sz = solver->sd_sz;
    nw = solver->nw;
    n = solver->n;
    k = solver->k;
-   values = solver->values;
-   weights = solver->weights;
+   item = solver->items;
    data_base = (char *) solver->data;
 
    /* SOLVE */
-   for (i = 0; i < n; i++)
+   for (i = 0; i < n; i++, item++)
      {
-        v = values[i];
-        w = weights[i];
+        v = item->value;
+        w = item->weight;
         c = (SolverData *) (data_base + (sd_sz * k));
         p = (SolverData *) (data_base + (sd_sz * (k - w)));
 
@@ -96,21 +100,23 @@ static void print(Solver* solver)
    int b;
    int i;
    int v, w;
+   Item *item;
    SolverData *sol;
 
    v = 0;
    w = 0;
    sol = (SolverData *) (((char *) solver->data) + (solver->sd_sz * solver->k));
 
-   printf("%d %d\n", sol->v, 1);
-   for (i = 0; i < solver->n; i++)
+   item = solver->items;
+   printf("%d %d\n", sol->v, 0);
+   for (i = 0; i < solver->n; i++, item++)
      {
         b = get_bit(sol->bits, i);
         printf("%d ", b);
         if (b)
           {
-             v += solver->values[i];
-             w += solver->weights[i];
+             v += item->value;
+             w += item->weight;
           }
      }
    printf("\n");
@@ -127,7 +133,7 @@ int main(int argc, char** argv, char** env)
    Solver solver;    // solver
 
    int i;
-   int *vp, *wp;
+   Item *item;
    SolverData *data;
 
    if(argc < 2)
@@ -153,30 +159,19 @@ int main(int argc, char** argv, char** env)
    if (debug) printf("  K:%d N:%d\n", solver.k, solver.n);
 
    /* allocate */
-   solver.values = calloc(solver.n, sizeof(int));
-   if (!solver.values)
-     {
-        fprintf(stderr, "ERROR: values calloc\n");
-        return EXIT_FAILURE;
-     }
-   vp = solver.values;
-
-   solver.weights = calloc(solver.n, sizeof(int));
-   if (!solver.weights)
+   solver.items = calloc(solver.n, sizeof(Item));
+   if (!solver.items)
      {
-        free(solver.values);
-        fprintf(stderr, "ERROR: weights calloc\n");
+        fprintf(stderr, "ERROR: items calloc\n");
         return EXIT_FAILURE;
      }
-   wp = solver.weights;
 
    solver.nw = (solver.n / WORD_BITS + 1);
    solver.sd_sz = sizeof(SolverData) + (solver.nw * sizeof(word_t));
    solver.data= calloc((solver.k + 1), solver.sd_sz);
    if (!solver.data)
      {
-        free(solver.values);
-        free(solver.weights);
+        free(solver.items);
         fprintf(stderr, "ERROR: solver calloc\n");
         return EXIT_FAILURE;
      }
@@ -187,22 +182,24 @@ int main(int argc, char** argv, char** env)
      }
 
    /* read items */
-   for (i = 0; i < solver.n; i++)
-     fscanf(fp, "%d %d\n", vp++, wp++);
+   item = solver.items;
+   for (i = 0; i < solver.n; i++, item++)
+     fscanf(fp, "%d %d\n", &item->value, &item->weight);
    fclose(fp);
 
    if (debug)
      {
+        item = solver.items;
         printf("     index    value   weight\n");
-        for (i = 0; i < solver.n; i++)
-          printf("  % 8d % 8d % 8d\n", i, solver.values[i], solver.weights[i]);
+        for (i = 0; i < solver.n; i++, item++)
+          printf("  % 8d % 8d % 8d\n", i, item->value, item->weight);
      }
 
    solve(&solver);
    print(&solver);
 
-   free(solver.values);
-   free(solver.weights);
+   free(solver.items);
+   free(solver.data);
 
    return EXIT_SUCCESS;
 }