问题描述
01背包问题是特别经典的一个DP（DynamicProgramming）动态规划问题。在M件物品取出若干件放在空间为W的背包里，每件物品的体积为W1，W2至Wn，与之相对应的价值为P1，P2至Pn。也就是往包里放总价值最大的东西，所以一个物品拿与不拿就成了选择的问题。例如有如下物品（2/3）、（4/4）、（3/3）三样物品（w/p），背包空间5，如果拿价值最大的（4/4），则拿不了其他东西，这时选择拿（2/3）和（3/3）则可以达到价值最大为6。那么相对于多个物品进行选择时就没那么容易了。
求解思路
1. 将原问题分解为子问题（子问题和原问题形式相同），01背包中一个状态就是M个物体中第i个是否放入体积为W背包中。
首先定义一张二维表T[M][W]，T[i][j]表示前i个物品放入空间大小为j的背包中最大的价值。这里的子问题就是前i个物品放入容量为j（j<=W），这里划分多个j是为了方便计算背包容量W减去某个物品空间剩余空间的大小，减少重复计算。
2. 考虑初始时的状态（边界问题）。
很显然，T[0][...]第0行全为0，T[...][0]第0列也全为0，即0个可选物品或者背包空间为0都不能放入物品。
3. 确定状态转移方程，如何从一个或多个已知状态求出另一个未知状态的值。
那么，如何根据前面计算出的值，推导出后面的值。
状态转移方程：T[i][j]=max{T[i-1][j]，T[i-1][j-w[i]]+p[i]}
上面的方程表达的就是第i个物品是否放入容量为j的背包中，比较两个值，第一个值就是背包容量为j时，前i-1个物品放入后最大的价值，第二个值是背包容量为j-w[i]时（假设背包容量为j时放入物品i），前i-1个物品放入后最大的价值加上物品i的价值，这两个值哪个更大，则就是T[i][j]的值。
代码
public static void main(String[]args) {
int bagVolume = 10;
int[][] T = new int[7][bagVolume + 1];//表示第i个物品放入容量j的最大值，背包容量20
int[] p = new int[]{0, 2, 5, 3, 10, 4, 9};//第i个物品的价值
int[] w = new int[]{0, 1, 3, 2, 6, 2, 5};//第i个物品的体积
for (int i = 1;i<p.length;i++){
for (int j=1;j<=bagVolume;j++){
if (j<w[i]){//如果当前背包容量大小放不下第i个物品
T[i][j]=T[i-1][j];
}else {
T[i][j]=Math.max(T[i- 1][j], T[i - 1][j - w[i]] + p[i]);
}
}
}
System.out.println("最大价值为："+T[6][bagVolume]);
//输出查看T表
for (int i=0;i<T.length;i++){
for (int j=0;j<T[0].length;j++){
System.out.format("%4d",T[i][j]);
}
System.out.println();
}
}
输出为
最大价值为：18
i\j |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
0 |
2 |
2 |
5 |
7 |
7 |
7 |
7 |
7 |
7 |
7 |
3 |
0 |
2 |
3 |
5 |
7 |
8 |
10 |
10 |
10 |
10 |
10 |
4 |
0 |
2 |
3 |
5 |
7 |
8 |
10 |
12 |
13 |
15 |
17 |
5 |
0 |
2 |
4 |
6 |
7 |
9 |
11 |
12 |
14 |
16 |
17 |
6 |
0 |
2 |
4 |
6 |
7 |
9 |
11 |
13 |
15 |
16 |
18 |