diff options
| -rw-r--r-- | 01-knapsack/ks_dp-ng.c | 15 |
1 files 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); } |