Knapsack
``````/*************************************************************************
*  Compilation:  javac Knapsack.java
*  Execution:    java Knapsack N P W
*
*  Generates an instance of the knapsack problem with N items,
*  profits between 0 and P-1, weights between 0 and W-1,
*  and solves it in O(NW) using dynamic programming.
*
*  %  java Knapsack 6 1000 2000
*  item    profit  weight  take
*  1       697     1248    false
*  2       547     224     false
*  3       815     776     false
*  4       342     495     true
*  5       893     1483    true
*  6       865     1251    false
*
*************************************************************************/

public class Knapsack {

public static void main(String args[]) {
int N = Integer.parseInt(args[0]);
int P = Integer.parseInt(args[1]);  // maximum profit
int W = Integer.parseInt(args[2]);  // maximum weight
int[] profit = new int[N+1];
int[] weight = new int[N+1];

// generate random instance, items 1..N
for (int n = 1; n <= N; n++) {
profit[n] = (int) (Math.random() * P);
weight[n] = (int) (Math.random() * W);
}

// opt[n][w] = max profit of packing items 1..n with weight limit w
// sol[n][w] = true if opt solution to pack items 1..n with weight limit w
//             includes item n
int[][] opt = new int[N+1][W+1];
boolean[][] sol = new boolean[N+1][W+1];
for (int n = 1; n <= N; n++) {
for (int w = 1; w <= W; w++) {
int option1 = opt[n-1][w];        // don't take item n
int option2 = Integer.MIN_VALUE;  // take item n
if (weight[n] < w) option2 = weight[n] + opt[n-1][w-weight[n]];
opt[n][w] = Math.max(option1, option2);
sol[n][w] = (option2 > option1);
}
}

// determine which items to take
boolean[] take = new boolean[N+1];
for (int n = N, w = W; n > 0; n--) {
if (sol[n][w]) { take[n] = true;  w = w - weight[n]; }
else           { take[n] = false;                    }
}

// print results
System.out.println("item" + "\t" + "profit" + "\t" + "weight" + "\t" + "take");
for (int n = 1; n <= N; n++)
System.out.println(n + "\t" + profit[n] + "\t" + weight[n] + "\t" + take[n]);
System.out.println();

}
}```
```
page revision: 0, last edited: 17 Oct 2012 21:22