/*
 * 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] 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.
 */
import java.io.*;
import java.util.*;
public class Knap01Grid
{
// ? ?  Show EACH knapsack from 1 up to final solution ? ?
   static final boolean DEBUG = false;

   static void knapSack01 (int maxWeight, boolean[] pack,
                           int [] weight, int [] value)
   {
      int         n = pack.length-1;
      boolean[][] trial = new boolean[maxWeight+1][n+1];
      int[]       bestVal = new int[maxWeight+1];
      int wt, k;

      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];
            System.arraycopy(trial[testWt], 0, trial[wt], 0, n+1);
            trial[wt][bestK] = true;
         }
         else // Can't get here, so finish using the wt-1 solution
            System.arraycopy(trial[wt-1], 0, trial[wt], 0, n+1);
         if ( DEBUG )
            showKnapSack (wt, trial[wt], weight, value);
      }
      System.arraycopy(trial[maxWeight], 0, pack, 0, n+1);
   }

   static void showKnapSack (int maxWeight, boolean[] pack,
                             int [] weight, int [] value)
   {  int sumWeight = 0, sumValue = 0,
          n = pack.length-1;

      System.out.println ("Optimal knapsack for " + maxWeight);
      for ( int k = 1; k <= n; k++ )
         if ( pack[k] )
         {  sumWeight += weight[k];
            sumValue  += value[k];
            System.out.println ("(" + weight[k] + ", " + value[k] + ")");
         }
      System.out.println ("Total weight:  " + sumWeight);
      System.out.println ("Total value:   " + sumValue);
   }

   public static void main ( String[] args ) throws Exception
   {  boolean [] pack;
      int [] weight, value;
      int k, n, maxWeight;
      String lineIn = args.length == 0 ?"BandP.txt" : args[0];
      Scanner inp = new Scanner(new File(lineIn));

      System.out.println ("Reading data from file " + lineIn);

      maxWeight = inp.nextInt();
      n = inp.nextInt();

      weight  = new int[n+1];
      value   = new int[n+1];
      pack    = new boolean[n+1];

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

      knapSack01 (maxWeight, pack, weight, value);

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