01背包问题
需要注意的问题：
- 对于01背包问题：每一件物品，要么不放要么只放一次
- 对于dp二维数组，第一维应该是物品数量，第二维才是体积或者重量
- 对于物品数量，遍历应该从1开始，并且dp【i】【w】 = Math.max(dp【i-1】【w】, dp【i-1】【w-vw【i】【0】】 + vw【i】【1】)，解释：dp【i】【w】，代表背包容量为w时，物品陈列为0~i-1这几个物品时背包所能装的最大重量，vw【i】【0】代表物品i-1的体积，vw【i】【1】代表物品i-1的重量。
思路：
- 首先对dp数组进行初始化，要想得到最终的结果，我们就要知道子问题的结果，例如上面提到的：如果要求得dp【i】【w】的值首先得知道dp【i-1】【w-vw【i】【0】】的值
- 对于物品i，实际有两种选择，第一种不放（包括背包容量不足以装下i），对于二维数组来说值就是当前列的上一行dp【i-1】【w】，第二种放：如果容量足够，那么就可以放，这时候的值应该是减掉物品i占用的体积所能放的最大重量加上物品i的重量，而最终还要比较在这种情况下，不放和放哪个大，取最大的哪个，之所以要比是因为：如果两个物品i-1和i，它们体积相同，质量不同，而且背包也只能装一个，那么最后就需要比较放i和不放i哪个大了
- 最后返回父问题的结果就ok了
- 当然如果理解起来很困难，那就将二维数组画成一个表格，从左到右，从上到下依次填充，不过实际上没必要这样，因为这种问题有点递归的意思在里面，正如对于递归没必要对每个细节都清楚，我们只需要知道递归做的工作是什么，边界值是什么，返回什么就行了，对于01背包也是，我们不用知道子问题最后的值是什么，我们只要知道父问题是子问题的值比较出来的就行了
真题链接：
解答：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 计算01背包问题的结果
* @param V int整型 背包的体积
* @param n int整型 物品的个数
* @param vw int整型二维数组 第一维度为n,第二维度为2的二维数组,vw[i][0],vw[i][1]分别描述i+1个物品的vi,wi
* @return int整型
*/
public int knapsack (int V, int n, int[][] vw) {
// write code here
int[][] dp = new int[n+1][V+1];
//i=0的时候代表没有物品，这时候不管背包的容量为多少，实际背包装的最大重量都应该为0
for(int i = 1; i<=n;i++){
//当背包容量为0的时候，不管有多少物品，背包都装不下，所以也是0
for(int j = 1;j<=V;j++){
if(j<vw[i-1][0]){
dp[i][j] = dp[i-1][j];
}else{
dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-vw[i-1][0]]+vw[i-1][1]);
}
}
}
return dp[n][V];
}