目标和
494. 目标和
给定一个非负整数数组，a1, a2, …, an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。
返回可以使最终数组和为目标数 S 的所有添加符号的方法数。
示例：
输入：nums: [1, 1, 1, 1, 1], S: 3 输出：5 解释：
-1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3
一共有5种方法让最终目标和为3。
提示：
数组非空，且长度不会超过 20 。
初始的数组的和不会超过 1000 。
保证返回的最终结果能被 32 位整数存下。
思路
- 转换成01背包问题
考虑到每个数字不管是取正数还是取负数，都只能取一次，所以考虑使用01背包解决 - 可以转换一下，设有正数值为 x ，那么负数的数值就为 sum-x ，可以列出等式
x-(sum-x) = S,所以x = (s+sum)/2问题也就转换成了装满容量为x的背包，有几种方法 也就是说target = bagSize = x - 本题还需特判：当S>sum时，肯定没有方法，如果x不为整数，也不符合题目要求
分五步走：
- 确定dp数组及其下标含义：dp[j]表示装满容量为j的背包的方法数
- 推导dp公式：不考虑nums[i]的情况下，有dp[j-nums[i]]中方法（个人理解不考虑nums[i],相当于nums[i]是一个负数，不算进正数）
考虑到nums[i].就有dp[j]种方法.
所以dp[j] = dp[j] + dp[j-nums[i]] - 初始化dp数组：dp[0] = 1，因为背包容量为0时，也可以有装入0个物品这一种方法
- 确定遍历方向：dp[j] 由 dp[j-nums[i]] 推出，所以遍历方向是从左往右，先遍历物品，再倒序遍历背包容量
- 举例推导dp数组
代码
public int findTargetSumWays(int[] nums, int S) {
int sum = 0;
for(int i=0;i<nums.length;i++) sum += nums[i];
if(S>sum) return 0;
if((S+sum)%2 != 0) return 0;
int bagSize = (S+sum)/2;
int[] dp = new int[bagSize+1];
dp[0] = 1;
for(int i=0;i<nums.length;i++){
for(int j=bagSize;j>=nums[i];j--){
dp[j] += dp[j-nums[i]];
}
}
return dp[bagSize];
}
总结
此题考查的是装满背包容量为x有多少种方法，需要考虑到每个数字虽然都要取，但是都只能取一次，并且每个数字只有正负两种情况，所以考虑使用01背包，同时要将问题转换为求背包容量上来，即求背包容量为x,有多少种方法装物品，或者能否将背包装满，或者装满背包之后剩下多少重量的物品
01背包问题主要是要找到以下几个信息：
- 背包装满的条件是什么(target是多少)，背包容量bagSize是多少
- 每个物品重量和价值是什么
- 每个物品是否只能拿一次，或者每个物品只有拿一个或不拿两个选择
一和零
474.一和零
给你一个二进制字符串数组 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 。
示例 2：
输入：strs = [“10”, “0”, “1”], m = 1, n = 1
输出：2
解释：最大的子集是 {“0”, “1”} ，所以答案是 2 。
提示：
1 <= strs.length <= 600
1 <= strs[i].length <= 100
strs[i] 仅由 ‘0’ 和 ‘1’ 组成
1 <= m, n <= 100
思路
- 此题strs中的一个个串就是物品，然后m和n就是背包的容量，只不过背包变成二维的了
所以还是01背包问题
分五步走：
- 确定dp数组及其下标的含义：dp[i][j]代表最多有i个0，j个1的的strs子集的大小
- 推导dp方程：很明显dp数组的每个值都是装载该子串的1和0的结果+1,即
dp[i-zeroNum][j-oneNum]+1，由于遍历过程中要求的是最大子串个数，所以取最大值
dp[i][j] = max(dp[i][j],dp[i-zeroNum][j-oneNum]+1) - 初始化：背包容量为0时，装载数量为0，参考01背包其余也为0
- 遍历方向：先遍历物品，再逆序遍历背包容量，
- 举例推导dp数组
代码
public int findMaxForm(String[] strs, int m, int n) {
int[][] dp = new int[m+1][n+1];
for(String s:strs){//遍历物品
int oneNum = 0,zeroNum = 0;
for(char c:s.toCharArray()){
if(c == '1') oneNum++;
else zeroNum++;
}
for(int i=m;i>=zeroNum;i--){//遍历背包容量
for(int j=n;j>=oneNum;j--){
dp[i][j] = Math.max(dp[i][j],dp[i-zeroNum][j-oneNum]+1);
}
}
}
return dp[m][n];
}
总结
本题难点在于，背包的容量是二维的，所以需要使用二维数组来装载物品
装载顺序没有影响，主要需要明确物品的重量和价值
本题每个物品的重量为0的个数和1的个数，价值为1
转换成背包容量为n个1，m个0所能装的物品个数最大(价值最高)即可。