需求：对于一组不同重量、不同价值、不可分割的物品，我们需要选择一些装入背包，计算满足背包重量的前提下，装入背包的物品的最大价值是多少呢？
之所以叫0-1背包问题，就是因为物品不可分割。
相比前面的0-1背包问题，这里的升级版问题引入了物品价值，考虑的维度多了一个。
我们先回顾一下之前讲过的回溯算法的逻辑：
动态规划的实现逻辑是根据前面计算的状态结果来决定后续计算，但是不考虑之前的结果是如何计算的，既然要根据前面的状态，那么就要把前面计算的状态结果保存下来，这就需要申请额外的空间。
动态规划也有公式，就跟递归有递归公式一样，写动态规划就是写动态规划公式。
简单来说动态规划的重点：
1、基于前面的计算结果来进行后续计算。
2、编写动态规划公式。
我们来看代码，理解一下上面的理论。
public class BeiBao_DongTaiGuiHua2 {
// 物品重量
private static final int[] weight = {2, 2, 4, 6, 3};
// 物品的价值
private static int[] value = {5, 2, 8, 12, 6};
// 物品个数
private static final int n = 5;
// 背包承受的最大重量
private static final int w = 9;
public static void main(String[] args) {
BeiBao_DongTaiGuiHua2.getMaxWeight();
/*System.out.println("-------------------------------------");
BeiBao_DongTaiGuiHua2.getMaxWeight2();
System.out.println("-------------------------------------");
BeiBao_DongTaiGuiHua2.getMaxWeight3();*/
}
public static void getMaxWeight() {
//定义标记数组
int[][] wFlag = new int[n][w + 1];
for (int x = 0; x < wFlag.length; x++) {
for (int y = 0; y < wFlag[x].length; y++) {
wFlag[x][y] = -1;
}
}
//初始化第一个物品的标记结果
wFlag[0][0] = 0;
if (weight[0] < w) {
wFlag[0][weight[0]] = value[0];
}
//动态规划计算背包结果
for (int x = 1; x < n; x++) {
//第x个商品不放进背包
for (int y = 0; y <= w; y++) {
if (wFlag[x - 1][y] >= 0) {
wFlag[x][y] = wFlag[x - 1][y];
}
}
//第x个商品放进背包
for (int y = 0; y <= w - weight[x]; y++) {
System.out.println("当前第:" + (x + 1) + "个商品,当前计算位置:" + y);
if (wFlag[x - 1][y] >= 0) {
if (wFlag[x - 1][y] + value[x] > wFlag[x][y + weight[x]]) {
wFlag[x][y + weight[x]] = wFlag[x - 1][y] + value[x];
}
}
}
System.out.println("------------------------------------------");
}
//打印结果
int max = Integer.MIN_VALUE;
for (int x = w; x >= 0; x--) {
if (max < wFlag[n - 1][x]) {
max = wFlag[n - 1][x];
}
}
System.out.println("背包中最大重量为:" + max);
}
}
/* 输出
当前第:2个商品,当前计算位置:0
当前第:2个商品,当前计算位置:1
当前第:2个商品,当前计算位置:2
当前第:2个商品,当前计算位置:3
当前第:2个商品,当前计算位置:4
当前第:2个商品,当前计算位置:5
当前第:2个商品,当前计算位置:6
当前第:2个商品,当前计算位置:7
------------------------------------------
当前第:3个商品,当前计算位置:0
当前第:3个商品,当前计算位置:1
当前第:3个商品,当前计算位置:2
当前第:3个商品,当前计算位置:3
当前第:3个商品,当前计算位置:4
当前第:3个商品,当前计算位置:5
------------------------------------------
当前第:4个商品,当前计算位置:0
当前第:4个商品,当前计算位置:1
当前第:4个商品,当前计算位置:2
当前第:4个商品,当前计算位置:3
------------------------------------------
当前第:5个商品,当前计算位置:0
当前第:5个商品,当前计算位置:1
当前第:5个商品,当前计算位置:2
当前第:5个商品,当前计算位置:3
当前第:5个商品,当前计算位置:4
当前第:5个商品,当前计算位置:5
当前第:5个商品,当前计算位置:6
------------------------------------------
背包中最大重量为:19
*/
标记状态的数据wFlag的状态推演：
简单背包问题中我们还将wFlag标记数组从二维优化到了一维，但是在背包升级问题中，就不能优化了，因为这里我们要计算的是最大价值，wFlag的类型也从boolean[][]变为了int[][]。
wFlag[][]中存的是对应的物品价值。