• We can solve this with dynamic programming
• Step 1 is work out a recurrance:
  Let K(i,m) denote the max profit you can get using items 1..i in a knapsack of size m, P_i the profit for object i, and W_i the weight for object i. Then:

  K(i, m) = greater of K(i-1, m) and P_i + K(i-1, m-W_i)

• Step 2 is compute the number of subproblems to be computed. In this case it is the number of K(i,m) values, ie n*w - where n is the total number of objects and w is the initial capacity of the knapsack.
• Step 3 - work out the best order to evaluate the subproblems - in this case

     for i=1..n
        for m=0..w
           array [i,m] = compute K(i,m)
  

• Here is a table for Knapsack01 with capacity 6, and 3 objects with (profit,weight) as follows: (5,4) (2,3) (1,2)

  	0	1	2	3	4	5	6
  i=1	0	0	0	0	5	5	5
  i=2	0	0	0	2	5	5	5
  i=3	0	0	1	2	5	5	6

  So the maximum profit is 6.

• Check out this sample

Knapsack01.java

//
// Knapsack-0/1
//
// We have a knapsack that can hold a total weight W, as well as a set of N
// items that each have a weight wi and a value pi. The items are unique: we
// can pack one or leave it behind, but there is no question of taking multiples
// of an item. We want to pack our knapsack with items of greatest possible
// total value, and with total weight <= W.

public class Knapsack01 {

public static void main(String[] args) {

   // Read command line arguments. The first is the maximum capacity.
   // The next are pairs of (weight, value) for each object

   if (args.length  [  [..]]");
      System.exit(1);
   }

   int maxCapacity = Integer.parseInt(args[0]);
   int numItems = (args.length - 1) / 2;
   int[] weight = new int[numItems];
   int[] value	= new int[numItems];

   for (int i=0; i<numItems; i++) {
      weight[i] = Integer.parseInt(args[1+2*i]);
      value[i]	= Integer.parseInt(args[2+2*i]);
   }

   // Complete the first row of the subsolution matrix: if we can only
   // take item zero, what is our maximum profit for the possible
   // knapsack sizes 0, 1, 2, ..., max_capacity.
   int[][] subSolutions = new int[numItems][maxCapacity+1];

   for (int capacity=0; capacity<weight[0]; capacity++)
      subSolutions[0][capacity] = 0;
   for (int capacity=weight[0]; capacity<=maxCapacity; capacity++)
      subSolutions[0][capacity] = value[0];

   // And initialise the first column (can take naothing if capacity=0)
   for (int i=0; i<numItems; i++)
      subSolutions[i][0] = 0;


   // Now complete the remaining rows of the matrix in turn. In each new
   // row we allow ourselves to consider one additional item. Within each
   // row we consider larger knapsacks as we go from left to right.
   for (int item = 1; item<numItems; item++)
      for (int capacity = 1; capacity <= maxCapacity; capacity++) {

	 if (weight[item]  capacity)
	    subSolutions[item][capacity] = subSolutions[item-1][capacity];
	 else {
	    int valueA = subSolutions[item-1][capacity];
	    int valueB = value[item] +
			 subSolutions[item-1][capacity-weight[item]];

	    subSolutions[item][capacity] = Math.max(valueA, valueB);
	 }
      } // end for



   System.out.println("Maximum capacity: " + maxCapacity);
   System.out.println("   Maximum value: " + subSolutions[numItems-1][maxCapacity]);

/*
   for (int item=0; item<numItems; item++) {
      for (int capacity=0; capacity<=maxCapacity; capacity++)
	 System.out.print(subSolutions[item] [capacity] + "  ");
      System.out.println();
   }
*/

} // end main
} // end class

// Knapsack-0/1

// We have a knapsack that can hold a total weight W, as well as a set of N
// items that each have a weight wi and a value pi. The items are unique: we
// can pack one or leave it behind, but there is no question of taking multiples
// of an item. We want to pack our knapsack with items of greatest possible
// total value, and with total weight <= W.

public class Knapsack01 {

public static void main(String[] args) {

// Read command line arguments. The first is the maximum capacity.
// The next are pairs of (weight, value) for each object

if (args.length < 1) {
System.out.println(
"Usage: java Knapsack01 <capacity> [<weight> <value> [..]]");
System.exit(1);
}

int maxCapacity = Integer.parseInt(args[0]);
int numItems = (args.length - 1) / 2;
int[] weight = new int[numItems];
int[] value = new int[numItems];

for (int i=0; i<numItems; i++) {
weight[i] = Integer.parseInt(args[1+2*i]);
value[i] = Integer.parseInt(args[2+2*i]);
}

// Complete the first row of the subsolution matrix: if we can only
// take item zero, what is our maximum profit for the possible
// knapsack sizes 0, 1, 2, ..., max_capacity.
int[][] subSolutions = new int[numItems][maxCapacity+1];

for (int capacity=0; capacity<weight[0]; capacity++)
subSolutions[0][capacity] = 0;
for (int capacity=weight[0]; capacity<=maxCapacity; capacity++)
subSolutions[0][capacity] = value[0];

// And initialise the first column (can take naothing if capacity=0)
for (int i=0; i<numItems; i++)
subSolutions[i][0] = 0;


// Now complete the remaining rows of the matrix in turn. In each new
// row we allow ourselves to consider one additional item. Within each
// row we consider larger knapsacks as we go from left to right.
for (int item = 1; item<numItems; item++)
for (int capacity = 1; capacity <= maxCapacity; capacity++) {

if (weight[item] > capacity)
subSolutions[item][capacity] = subSolutions[item-1][capacity];
else {
int valueA = subSolutions[item-1][capacity];
int valueB = value[item] +
subSolutions[item-1][capacity-weight[item]];

subSolutions[item][capacity] = Math.max(valueA, valueB);
}
} // end for



System.out.println("Maximum capacity: " + maxCapacity);
System.out.println(" Maximum value: " + subSolutions[numItems-1][maxCapacity]);

/*
for (int item=0; item<numItems; item++) {
for (int capacity=0; capacity<=maxCapacity; capacity++)
System.out.print(subSolutions[item] [capacity] + " ");
System.out.println();
}
*/

} // end main
} // end class