需求：对于一组不同重量、不可分割的物品，我们需要选择一些装入背包，在满足背包最大重量限制的前提下，背包中物品总重量的最大值是多少呢？
之所以叫0-1背包问题，就是因为物品不可分割。
动态规划的实现逻辑是根据前面计算的状态结果来决定后续计算，但是不考虑之前的结果是如何计算的，既然要根据前面的状态，那么就要把前面计算的状态结果保存下来，这就需要申请额外的空间。
动态规划也有公式，就跟递归有递归公式一样，写动态规划就是写动态规划公式。
简单来说动态规划的重点：
1、基于前面的计算结果来进行后续计算。
2、编写动态规划公式。
我们来看代码，理解一下上面的理论。
/**
* 背包0-1问题 动态规划
*
*/
public class BeiBao_DongTaiGuiHua {
// 物品重量
private static final int[] weight = {2,2,4,6,3};
// 物品个数
private static final int n = 5;
// 背包承受的最大重量
private static final int w = 9;
public static void main(String[] args) {
BeiBao_DongTaiGuiHua.getMaxWeight();
}
public static void getMaxWeight() {
//定义标记数组
boolean[][] wFlag = new boolean[n][w+1];
//初始化第一个物品的标记结果
wFlag[0][0] = true;
if(weight[0]<w) wFlag[0][weight[0]] = true;
//动态规划计算背包结果
for(int x=1; x<n; x++) {
//第x个商品不放进背包
for(int y=0; y<=w; y++) {
if(wFlag[x-1][y]) {
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]) {
wFlag[x][y+weight[x]] = true;
}
}
System.out.println("------------------------------------------");
}
//打印结果
for(int x=w; x>=0; x--) {
if(wFlag[n-1][x]) {
System.out.println("背包中最大重量为:" + x);
return;
}
}
}
}
/* 输出
当前第: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
------------------------------------------
背包中最大重量为:9
*/
通过计算我们看到输出的结果是9，动态规划的计算公式是：
if(wFlag[x-1][y] == true)
wFlag[x-1][y+weight[x] = true标记状态的数据wFlag的状态推演：
初始状态
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
第一个物品不放和放入背包（下标为0的物品）
1 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
第二个物品不放和放入背包（下标为1的物品）
1 0 1 0 0 0 0 0 0 0
1 0 1 0 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
第三个物品不放和放入背包（下标为2的物品）
1 0 1 0 0 0 0 0 0 0
1 0 1 0 1 0 0 0 0 0
1 0 1 0 1 0 1 0 1 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0第四和第五以此类推…
动态规划的代码中我们发现使用了一个二维数组，我们其实还可以对动态规划的计算空间进行优化，将二维数组改为一维数组。
代码如下：
/**
* 优化标记空间，从二维数据变为一维数组
*/
public static void getMaxWeight2() {
//定义标记数组
boolean[] wFlag = new boolean[w+1];
//初始化第一个物品的标记结果
wFlag[0] = true;
if(weight[0]<w) wFlag[weight[0]] = true;
//动态规划计算背包结果
for(int x=1; x<n; x++) {
//第x个商品放进背包
for(int y=0; y<=w-weight[x]; y++) {
System.out.println("当前第:"+(x+1)+"个商品,当前计算位置:"+y);
if(wFlag[y]) {
wFlag[y+weight[x]] = true;
}
}
System.out.println("------------------------------------------");
}
//打印结果
for(int x=w; x>=0; x--) {
if(wFlag[x]) {
System.out.println("背包中最大重量为:" + x);
return;
}
}
}