From c9808b401cd93fa6959dbf6a66df49343979f8ff Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?J=C3=A9r=C3=A9my=20Zurcher?= <jeremy@asynk.ch>
Date: Wed, 3 Jul 2013 22:49:09 +0200
Subject: Discrete : 01-knapsack: compute capacity loop lower_bound

 - reduce by 50% the iteration count
   when items are sorted by value or weight
 - global 2% speed up only as loop does nothing realy
---
 01-knapsack/ks_dp-ng.c | 15 +++++++++++++--
 1 file changed, 13 insertions(+), 2 deletions(-)

diff --git a/01-knapsack/ks_dp-ng.c b/01-knapsack/ks_dp-ng.c
index c2f7aa4..c2216fc 100644
--- a/01-knapsack/ks_dp-ng.c
+++ b/01-knapsack/ks_dp-ng.c
@@ -31,6 +31,7 @@ typedef struct _Solver
 {
    int k;               /* capacity */
    int n;               /* items # */
+   int w_sum;           /* sum of input items weight */
    InputItem *items;    /* items */
    SolverItem *column;  /* solver column */
 } Solver;
@@ -91,6 +92,7 @@ static void solve(Solver* solver)
    int n, k;
    int v, w;
    int i, j;
+   int min_c, lower_bound;
    const InputItem *item;
    SolverItem *data;
    const SolverItem *up_left;
@@ -99,6 +101,7 @@ static void solve(Solver* solver)
 
    n = solver->n;
    k = solver->k;
+   min_c = solver->w_sum;
 
    if (debug > 2)
      {
@@ -116,7 +119,13 @@ static void solve(Solver* solver)
         data = solver->column + solver->k;
         up_left = solver->column + (solver->k - w);
 
-        for (j = k; j >= w; j--, data--, up_left--)
+        // this computes the top-left bottom-right diagonal,
+        // values above this don't need to be computed
+        min_c -= w;
+        lower_bound = (k - min_c);
+        if (lower_bound < w)
+          lower_bound = w;
+        for (j = k; j >= lower_bound; j--, data--, up_left--)
           {
              counter++;
 
@@ -254,11 +263,13 @@ int main(int argc, char** argv, char** env)
      }
 
    /* read items */
+   solver.w_sum = 0;
    item = solver.items;
    for (i = 0; i < solver.n; i++, item++)
      {
         item->i = i;
         fscanf(fp, "%d %d\n", &item->v, &item->w);
+        solver.w_sum += item->w;
      }
    fclose(fp);
 
@@ -297,7 +308,7 @@ int main(int argc, char** argv, char** env)
               printf(" desc\n");
           }
         item = solver.items;
-        printf("     index    Value   Weight\n");
+        printf("     index    Value   Weight (sum %d)\n", solver.w_sum);
         for (i = 0; i < solver.n; i++, item++)
           printf("  % 8d % 8d % 8d\n", item->i, item->v, item->w);
      }
-- 
cgit v1.1-2-g2b99