1.1 题目
有 N 件物品和一个容量为 V 的背包。放入第 i 件物品耗费的费用是 Ci1，得到的
价值是 Wi。求解将哪些物品装入背包可使价值总和最大。
1.2 基本思路
这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。
用子问题定义状态：即 F [i; v] 表示前 i 件物品恰放入一个容量为 v 的背包可以获得
的最大价值。则其状态转移方程便是：
F[i,v] = max{F[i-1,v],F[i-1,v-Ci]+Wi}
这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。所
以有必要将它详细解释一下：“将前 i 件物品放入容量为 v 的背包中”这个子问题，若只考虑第 i 件物品的策略（放或不放），那么就可以转化为一个只和前 i − 1 件物品相关
的问题。如果不放第 i 件物品，那么问题就转化为“前 i − 1 件物品放入容量为 v 的背
包中”，价值为 F [i − 1; v]；如果放第 i 件物品，那么问题就转化为“前 i − 1 件物品放
入剩下的容量为 v − Ci 的背包中”，此时能获得的最大价值就是 F [i − 1; v − Ci] 再加上
通过放入第 i 件物品获得的价值 Wi。
代码如下：
优化：
发现这个二维数组可以用一维数组表示，由于有些值只用过一次没有必要保存
于是就写出了这个
for(i=1;i<=n;i++)
for(j=w[i];j<=m;j++)
dp[j]=max{dp[j],dp[j-w[i]]+v[i]};
但是注意到上面二维的代码中dp[i]是由dp[i-1]推出的，如果直接改成一维的就会出现重复选择物品的现象，即：dp[j] = max{dp[j],dp[i][j-w[i]]+v[i]};
这是因为在j从小到大遍历时，出现dp[i][j-w[i]]比dp[i][j]更先遍历得到值;而dp[i][j-w[i]]已经选择过了第i个元素。因此，这么做重复选择了i。变成了完全背包问题。逆序推使得更小的索引更后遍历。能够保证 dp[j-c[i]] 保存的是状态是 dp[i-1][j-c[i]] ，也就是每个物品只被使用了一次；顺序的话 dp[j-w[i]] 保存的是 dp[i][j-w[i]] ，每个物品有可能被使用多次，也就是完全背包问题的解法。
将代码改成：
for(i=1;i<=n;i++)
for(j=m;j>=w[i];j--)
dp[j]=max{dp[j],dp[j-w[i]]+v[i]};
例题：
https://leetcode-cn.com/problems/ones-and-zeroes/
474. 一和零
难度中等284
给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
请你找出并返回 strs 的最大子集的大小，该子集中 最多 有 m 个 0 和 n 个 1 。
如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。
示例 1：
输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
输出：4
解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。
其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。
</pre>
示例 2：
输入：strs = ["10", "0", "1"], m = 1, n = 1
输出：2
解释：最大的子集是 {"0", "1"} ，所以答案是 2 。
</pre>
提示：
1 <= strs.length <= 6001 <= strs[i].length <= 100-
strs[i]仅由'0'和'1'组成 1 <= m, n <= 100
代码：
class Solution {
public int findMaxForm(String[] strs, int m, int n) {
// 能取几个;
// dp[i][j][k] 表示：第0~i个物品，j个0，K个1的限制，最多能取几个;
int[][] dp = new int[m+1][n+1];
if(strs.length==0){return 0;}
for(int i=0;i<strs.length;i++){
int numsZero = 0;
for(int l=0;l<strs[i].length();l++){
if(strs[i].charAt(l)=='0'){
numsZero++;
}
}
int numsOne = strs[i].length() - numsZero;
for(int j=m;j>=numsZero;j--){
for(int k=n;k>=numsOne;k--){
dp[j][k] = Math.max(dp[j][k],dp[j-numsZero][k-numsOne]+1);
}
}
}
return dp[m][n];
}
}
