public class Main {
public static void main(String[] args) {
int[] w = {1,4,3};//物品的重量
int[] val = {1500,3000,2000};//物品的价格
int n = 4;//背包的最大容量
//dp[i][j]代表最大容量为i时的最大总价值
int[][] dp = new int[w.length+1][n+1];
//初始化
//没有物品的行
for (int i = 0; i < n+1; i++) {
dp[0][i] = 0;
}
//最大容量为0的列
for (int i = 0; i < w.length+1; i++) {
dp[i][0] = 0;
}
for (int i = 0; i < dp.length; i++) {
for (int j = 0; j < dp[i].length; j++) {
System.out.print(dp[i][j]+" ");
}
System.out.println();
}
for (int i = 1; i < dp.length; i++) {
for (int j = 1; j < dp[i].length; j++) {
if (w[i-1] > j) {
//物品的重量大于背包的最大容量
dp[i][j] = dp[i-1][j];
} else {
dp[i][j] = Math.max(dp[i-1][j],val[i-1]+dp[i-1][j-w[i-1]]);
}
}
}
System.out.println();
for (int i = 0; i < dp.length; i++) {
for (int j = 0; j < dp[i].length; j++) {
System.out.print(dp[i][j]+" ");
}
System.out.println();
}
System.out.println(dp[dp.length-1][dp[0].length-1]);
}
}
如何拿到最大价值组合的商品：
//记录放入商品的情况
int[][] path = new int[w.length+1][n+1];
// dp[i][j] = Math.max(dp[i-1][j],val[i-1]+dp[i-1][j-w[i-1]]);
if (dp[i-1][j] < val[i-1]+dp[i-1][j-w[i-1]) {
dp[i][j] = val[i-1]+dp[i-1][j-w[i-1];
path[i][j] = 1;
} else {
dp[i][j] = dp[i-1][j];
int i = path.length-1;
int j = path[0].length-1;
while (i >= 0 && j >= 0) {
if (path[i][j] == 1) {
System.out.printf("第%d个商品放入背包\n",i);
j -= w[i-1];
}
i--;
}
