import java.util.Arrays;
public class KnapsackProblem {
public static void main(String[] args) {
String[] name = {"Guitar","IPhone","Sound Equipment","Notebook"};
int[] weights = {1, 1, 4, 3};
int[] values = {1500, 2000, 3000, 2000};
int capacity = 4;
int itemNum = values.length;
int[][] dp = new int[itemNum + 1][capacity + 1];
for(int i = 0,j=1;j<5;j++){
dp[i][j] = j;
}
for (int i = 1; i <= itemNum; i++) {
for (int j = 1; j <= capacity; j++) {
if (weights[i - 1] > j) {
dp[i][j] = dp[i - 1][j];
} else {
dp[i][j] = Math.max(dp[i - 1][j], values[i - 1] + dp[i - 1][j - weights[i - 1]]);
}
}
}
for (int[] row : dp) {
System.out.println(Arrays.toString(row));
}
int i = itemNum;
int j = capacity;
while (i > 0 && j > 0) {
if (dp[i][j] != dp[i - 1][j]) {
System.out.printf("%s商品放入背包(price:%d)\n", name[i-1],values[i-1]);
j -= weights[i - 1];
}
i--;
}
}
}