/*
 * Dynamic programming solution of the 0/1 knapsack.
 *
 * Author:  Timothy Rolfe
 *
 * Instead of using the items one at a time across all weights,
 * this algorithm computes the complete solution vector for each
 * weight.  Consequently the matrix has (maxWt+1) rows of (n+1)
 * columns --- boolean trial[maxWeight+1][n+1].  Then there is a
 * vector bestVal[maxWeight+1] giving the value for each weight.
 *
 * When computing a potential solution, search through items and
 * only examine ones that will not exceed the current weight limit.
 * If the item does not exceed the current limit, check to see
 * whether this item is already being used in the earlier partial
 * solution:
 *
 * testWt = wt - weight[k];
 * if ( testWt >= 0 && ! trial[testWt][k] )
 *
 * The final check is to see if this would improve the best seen
 * so far --- bestVal[wt] <= value[k]+bestVal[testWt]
 * In this case, retain bestK=k and update bestVal[wt].
 *
 * Note that it is possible that there IS no bestK --- given the
 * items, a knapsack of this weight cannot be generated.  In that
 * case, just copy the (wt-1) knapsack.
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>     // memcpy

//#define DEBUG

enum { FALSE, TRUE };   // In case bool type not defined.

void showKnapSack (int maxWeight, int n, int* pack,
                          int * weight, int * value);

void knapSack01 (int maxWeight, int n, int* pack,
                 int* weight, int* value)
{
   int** trial;
   int*  bestVal;
   int wt, k;

   trial = (int**) calloc (maxWeight+1, sizeof *trial);
   for ( wt = 0; wt <= maxWeight; wt++ )
      trial[wt] = (int*) calloc (n+1, sizeof *trial[wt]);
   bestVal = (int*) calloc (maxWeight+1, sizeof *bestVal);

   for ( wt = 1; wt <= maxWeight; wt++ )
   {
      int bestK = 0, testWt;

      // Initial guess:  the knapsack for wt-1.
      bestVal[wt] = bestVal[wt-1];
      for ( k = 1; k <= n; k++ )
      {
         testWt = wt - weight[k];
         if ( testWt >= 0 && ! trial[testWt][k] )
            if ( bestVal[wt] < value[k]+bestVal[testWt] )
            {
               bestK = k;
               bestVal[wt] = value[k]+bestVal[testWt];
            }
      }
      if (bestK > 0)
      {
         testWt = wt - weight[bestK];
         memcpy (trial[wt], trial[testWt], (n+1)*sizeof *trial[wt]);
         trial[wt][bestK] = TRUE;
      }
      else // Can't get here, so finish using the wt-1 solution
         memcpy (trial[wt], trial[wt-1], (n+1)*sizeof *trial[wt]);
#ifdef DEBUG
      showKnapSack (wt, n, trial[wt], weight, value);
#endif
   }
   memcpy (pack, trial[maxWeight], (n+1)*sizeof *trial[maxWeight]);
   for ( wt = 0; wt <= maxWeight; wt++ )
      free(trial[wt]);
   free(trial);
   free(bestVal);
}

void sort(int * key, int * par, int n);

int main ( int argc, char* argv[] )
{  int * pack;
   int * weight, * value;
   int k, n, maxWeight;
   char* lineIn = argc == 1 ?"BandP.txt" : argv[1];
   FILE *inp = fopen (lineIn, "r");

   if ( inp == NULL )
   {  printf ("Open failed for %s\n", lineIn);  exit(-1);  }

   printf ("Reading data from file %s\n", lineIn);

   fscanf (inp, "%d", &maxWeight);
   fscanf (inp, "%d", &n);

   weight  = (int*) calloc (n+1, sizeof *weight);
   value   = (int*) calloc (n+1, sizeof *value);
   pack    = (int*) calloc (n+1, sizeof *pack);

   for ( k = 1; k <= n; k++ )
   {  fscanf (inp, "%d", &weight[k]);
      fscanf (inp, "%d", &value[k]);
      printf ("%d:  %d wt, %d val.\n", k, weight[k], value[k]);
   }

      sort ( weight, value, n+1 );

   knapSack01 (maxWeight, n, pack, weight, value);

   showKnapSack (maxWeight, n, pack, weight, value);

   printf ("\nPress ENTER to exit: ");
   scanf ("%c", &k);    // Access violation for argv[1]
   return 0;
}

void showKnapSack (int maxWeight, int n, int* pack,
                          int * weight, int * value)
{  int sumWeight = 0, sumValue = 0,
       k;

   printf ("Optimal knapsack for %d\n", maxWeight);
   for ( k = 1; k <= n; k++ )
      if ( pack[k] )
      {  sumWeight += weight[k];
         sumValue  += value[k];
         printf ("(%d, %d)\n", weight[k], value[k]);
      }
   printf ("Total weight:  %d\n", sumWeight);
   printf ("Total value:   %d\n", sumValue);
}

void swap (int * x, int p, int q)
{  int tmp = x[p];  x[p] = x[q];  x[q] = tmp;  }

// NOTE:  sort from [1] up to [n]
void sort(int * key, int * par, int n)
{  int lim,
       max,
       k;

   for ( lim = n-1; lim > 1; lim-- )
   {  for ( max = 1, k = 2; k <= lim; k++ )
         if ( key[max] < key[k] ||
              ( key[max] == key[k] && par[max] < par[k] ) )
            max = k;
      swap (key, max, lim);
      swap (par, max, lim);
   }
}