diff options
Diffstat (limited to '01-knapsack')
| -rw-r--r-- | 01-knapsack/ks_dp-ng.c | 103 |
1 files changed, 101 insertions, 2 deletions
diff --git a/01-knapsack/ks_dp-ng.c b/01-knapsack/ks_dp-ng.c index 9f98a0d..c2f7aa4 100644 --- a/01-knapsack/ks_dp-ng.c +++ b/01-knapsack/ks_dp-ng.c @@ -7,7 +7,12 @@ #define NONE -1 +enum { SORT_DESC = 0, SORT_ASC }; +enum { UNSORTED = 0, SORT_WR, SORT_VR, SORT_RW, SORT_RV}; + static int debug; +static int sort; +static int sort_order; typedef struct _InputItem { @@ -30,6 +35,57 @@ typedef struct _Solver SolverItem *column; /* solver column */ } Solver; +static int +item_cmp(const void *p1, const void *p2) +{ + int ret; + float r1, r2; + const InputItem *i1, *i2; + + i1 = (const InputItem *) p1; + i2 = (const InputItem *) p2; + + ret = ((sort_order == SORT_ASC) ? 1 : -1); + + if (sort == SORT_WR) + { + if (i1->w > i2->w) return ret; + if (i1->w < i2->w) return -ret; + } + else if (sort == SORT_VR) + { + if (i1->v > i2->v) return ret; + if (i1->v < i2->v) return -ret; + } + else // SORT_RW | SORT_RV + { + r1 = i1->v / (float)i1->w; + r2 = i2->v / (float)i2->w; + if (r1 > r2) return ret; + if (r1 < r2) return -ret; + } + + if (sort == SORT_RW) + { + if (i1->w > i2->w) return ret; + if (i1->w < i2->w) return -ret; + } + else if (sort == SORT_RV) + { + if (i1->v > i2->v) return ret; + if (i1->v < i2->v) return -ret; + } + else // SORT_WR | SORT_VR + { + r1 = i1->v / (float)i1->w; + r2 = i2->v / (float)i2->w; + if (r1 > r2) return ret; + if (r1 < r2) return -ret; + } + + return 0; +} + static void solve(Solver* solver) { int n, k; @@ -129,8 +185,10 @@ int main(int argc, char** argv, char** env) InputItem *item; debug = 0; + sort = UNSORTED; + sort_order = SORT_DESC; excpected_value = NONE; - while ((opt = getopt(argc, argv, "d:e:")) != -1) { + while ((opt = getopt(argc, argv, "d:e:s:S")) != -1) { switch (opt) { case 'd': debug = atoi(optarg); @@ -138,8 +196,14 @@ int main(int argc, char** argv, char** env) case 'e': excpected_value = atoi(optarg); break; + case 's': + sort = atoi(optarg); + break; + case 'S': + sort_order = SORT_ASC; + break; default: /* '?' */ - fprintf(stderr, "Usage: %s [-d level] input\n", + fprintf(stderr, "Usage: %s [falgs] input\n", argv[0]); return EXIT_FAILURE; } @@ -150,6 +214,9 @@ int main(int argc, char** argv, char** env) return EXIT_FAILURE; } + if (sort > SORT_RV) sort = UNSORTED; + if (sort_order > SORT_ASC) sort = SORT_DESC; + if (debug > 0) printf("%s\n", argv[optind]); fp = fopen(argv[optind], "r"); if (fp == NULL) @@ -195,8 +262,40 @@ int main(int argc, char** argv, char** env) } fclose(fp); + if (sort != UNSORTED) + qsort(solver.items, solver.n, sizeof(InputItem), item_cmp); + if (debug > 1) { + printf(" Items "); + if (sort == UNSORTED) + { + printf("unsorted\n"); + } + else + { + printf("sorted "); + switch(sort){ + case SORT_VR: + printf("Value,ratio(V/W)"); + break; + case SORT_WR: + printf("Weight,ratio(V/W)"); + break; + case SORT_RW: + printf("ratio(V/W),Weight"); + break; + case SORT_RV: + printf("ratio(V/W),Value"); + break; + default: + break; + } + if (sort_order == SORT_ASC) + printf(" asc\n"); + else + printf(" desc\n"); + } item = solver.items; printf(" index Value Weight\n"); for (i = 0; i < solver.n; i++, item++) |