diff options
| author | Jérémy Zurcher <jeremy@asynk.ch> | 2013-07-03 15:24:43 +0200 |
|---|---|---|
| committer | Jérémy Zurcher <jeremy@asynk.ch> | 2013-07-03 15:24:43 +0200 |
| commit | 436c6b62b2b6412ccbe214cb93f709f671acf06a (patch) | |
| tree | 12086cca6aef44e75e5cd3594e62ef8a42336ab1 /01-knapsack/ks_dp.c | |
| parent | 0c4cef741200f5f78a2079ddd54ad7ecd0c9ef90 (diff) | |
| download | coursera-436c6b62b2b6412ccbe214cb93f709f671acf06a.zip coursera-436c6b62b2b6412ccbe214cb93f709f671acf06a.tar.gz | |
Discrete : 01-knapsack: tighten loop bounds
Diffstat (limited to '01-knapsack/ks_dp.c')
| -rw-r--r-- | 01-knapsack/ks_dp.c | 13 |
1 files changed, 11 insertions, 2 deletions
diff --git a/01-knapsack/ks_dp.c b/01-knapsack/ks_dp.c index 6ed8d00..f40c770 100644 --- a/01-knapsack/ks_dp.c +++ b/01-knapsack/ks_dp.c @@ -37,6 +37,7 @@ typedef struct _Solver int k; // capacity int n; // items # int nw; // # bytes per bits array + int sum_w; // sum of item weight size_t sd_sz; // solver data size Item *items; // items SolverData *data; // solver data @@ -49,10 +50,12 @@ static void solve(Solver* solver) int i, j; int v, w; + int max_c, upper_bound; char *data_base; Item *item; SolverData *c, *p; + max_c = solver->sum_w; sd_sz = solver->sd_sz; nw = solver->nw; n = solver->n; @@ -68,7 +71,9 @@ static void solve(Solver* solver) c = (SolverData *) (data_base + (sd_sz * k)); p = (SolverData *) (data_base + (sd_sz * (k - w))); - for (j = k; j > 0; j--) + max_c -= w; + upper_bound = (((k - max_c) > w) ? (k - max_c) : w ); + for (j = k; j >= upper_bound; j--) { if (j < w) break; @@ -182,9 +187,13 @@ int main(int argc, char** argv, char** env) } /* read items */ + solver.sum_w = 0; item = solver.items; for (i = 0; i < solver.n; i++, item++) - fscanf(fp, "%d %d\n", &item->value, &item->weight); + { + fscanf(fp, "%d %d\n", &item->value, &item->weight); + solver.sum_w += item->weight; + } fclose(fp); if (debug) |