/* Dynamic programming iterative integer knapsack.
 *
 * Transformation of Sedgewick's algorithm to an iterative one
 * based on the implementation of change generation by Dumitru Ciubatii
 * http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProg
 */
public class SedgewickCiubatii
{  static int n;             // Number of items
   static int [] profit;     // Value of each item, [1]..[n]
   static int [] weight;     // Weight of each item, [1]..[n]

   static int knap(int c, int[] solution)
   {  int i, space, m, t,
          maxKnown[], itemKnown[];

      itemKnown = new int [c+1];
      maxKnown  = new int [c+1];
   // If Java didn't fill with zeroes we would need
   // java.util.Arrays.fill(maxKnown,flag);
      for ( m = 1; m <= c; m++ )
         for (i = 1; i <= n; i++)
            if ( (space = m-weight[i]) >= 0 )
            {  t = maxKnown[space] + profit[i];
               // Dummy:  wt 1, value 0
               if ( t >= maxKnown[m] )
               {  maxKnown[m]  = t;
                  itemKnown[m] = i;
               }
            }
   // State of solution[] is unknown, so
      java.util.Arrays.fill (solution, 0);
      for (m=c; m>0 ; m-=weight[itemKnown[m]] )
         solution[itemKnown[m]]++;
      return maxKnown[c];
   }

   // test program predominantly from Sahni, DSAAJ, Pgm 20.2, expanded
   public static void main(String [] args) throws Exception
   {  String filename = args.length == 0 ? "Book.txt" : args[0];
      java.util.Scanner inp = new java.util.Scanner(
                                  new java.io.File(filename) );

      int c = inp.nextInt(), // Capacity,
          wt,                // Weight accumulated during listing knapsack
          val,               // Value accumulated during listing knapsack
          solution[];

      n = inp.nextInt();     // Number of items
      profit = new int [n + 2];   // Adding a dummy wt 1 / val 0 item
      weight = new int [n + 2];
      solution = new int [n + 2];

      System.out.printf  ("Data taken from file %s\n\n", filename);
      System.out.println ("Capacity:  " + c);
      System.out.println ("\nAvailable items:");
      for (int i = 1; i <= n; i++)
      {  weight[i] = inp.nextInt();
         profit[i] = inp.nextInt();
         System.out.printf ("%d:  (%d wt, %d val)\n",
                            i, weight[i], profit[i]);
      }
      // Patch to insure that the knapsack CAN be filled
      n++;
      weight[n] = 1; profit[n] = 0;

      System.out.print("\nOptimal value is ");
      System.out.println(knap(c, solution));

      wt = val = 0;
      for ( int j = 1; j <= n; j++ )
         if ( solution[j] > 0 )
         {
            System.out.printf ("%d of item %d (%d wt, %d val)\n",
               solution[j], j, weight[j], profit[j] );
            wt  += solution[j] * weight[j];
            val += solution[j] * profit[j];
         }
      System.out.printf ("Total weight:  %d\nTotal profit:  %d\n",
         wt, val);
   }
}
/* Sample runs:

Data taken from file TestData.txt

Capacity:  12

Available items:
1:  (5 wt, 18 val)
2:  (2 wt, 6 val)
3:  (6 wt, 22 val)
4:  (1 wt, 1 val)
5:  (7 wt, 28 val)
6:  (1 wt, 2 val)

Optimal value is 46
1 of item 1 (5 wt, 18 val)
1 of item 5 (7 wt, 28 val)
Total weight:  12
Total profit:  46
_____________________________________

Data taken from file TestDataAlt.txt

Capacity:  12

Available items:
1:  (5 wt, 18 val)
2:  (2 wt, 6 val)
3:  (6 wt, 22 val)
4:  (1 wt, 1 val)
5:  (8 wt, 28 val)
6:  (1 wt, 2 val)

Optimal value is 44
2 of item 3 (6 wt, 22 val)
Total weight:  12
Total profit:  44
*/