Discrete : 01-knapsack: add sort capability to ks_dp-ng.c

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++)