这道题和第三十三天的题的解法差不多,只不过这次不用判断dp[target]是否等于target了,而是求dp[target]最大是多少。这道题要求剩下石头最小的质量是多少,那么就把他们分成两半,两半的重量足够接近的时候,剩下石头最小的质量就越接近0,因此求出背包容量为sum/2的背包,最多能装多少重量的石头,然后拿这个值减去sum可得到另外一半的重量 两个相减即可得到最终的结果。
class Solution {
public:
int lastStoneWeightII(vector<int>& stones) {
vector<int> dp(15001, 0);
int sum = 0;
for (int i = 0; i < stones.size(); i++) sum += stones[i];
int target = sum / 2;
for (int i = 0; i < stones.size(); i++) { // 遍历物品
for (int j = target; j >= stones[i]; j--) { // 遍历背包
dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
}
}
return sum - dp[target] - dp[target];
}
};
在回溯算法系列中,一起学过这道题目回溯算法:39. 组合总和 (opens new window)的录友应该感觉很熟悉,这不就是组合总和问题么?因为只有两个选择 +或者- 因此可以暴力回溯解答出来 但是时间会超时。下面是回溯的代码。
class Solution {
public:
vector<int> path;
void backtracking(vector<int>& nums, int startIndex, int& result, int target) {
if (path.size() == nums.size()) {
int sum = accumulate(path.begin(), path.end(), 0);
if (sum == target) result++;
}
for (int i = startIndex; i < nums.size(); i++) {
path.push_back(nums[i]);
backtracking(nums, i + 1, result, target);
path.pop_back();
path.push_back(-nums[i]);
backtracking(nums, i + 1, result, target);
path.pop_back();
}
}
int findTargetSumWays(vector<int>& nums, int target) {
int result = 0;
backtracking(nums, 0, result, target);
return result;
}
};
这道题目的数可以分为两个集合 一个全是正数一个全是负数
假设加法的集合总和为x,那么减法对应的总和就是sum - x。
所以我们要求的是 x - (sum - x) = target
x = (target + sum) / 2
此时问题就转化为,装满容量为x的背包,有几种方法,也就是装满正数的集合有几种方法。剩下的就是负数的集合
这里的x,就是bagSize,也就是我们后面要求的背包容量。 并且如果(target + sum) / 2不能整除的话那么说明就无法凑成结果为sum的正负数集合。
再回归到01背包问题,为什么是01背包呢?
因为每个物品(题目中的1)只用一次!
这次和之前遇到的背包问题不一样了,之前都是求容量为j的背包,最多能装多少。
本题则是装满有几种方法。其实这就是一个组合问题了。
1. 确定dp数组以及下标的含义
dp[j] 表示:nums[0]到nums[i]的数据里填满j(包括j)这么大容积的包,有dp[j]种方法
2. 确定递推公式
有哪些来源可以推出dp[j]呢?
只要搞到nums[i],凑成dp[j]就有dp[j - nums[i]] 种方法。
例如:dp[j],j 为5,
- 已经有一个1(nums[i]) 的话,有 dp[4]种方法 凑成 容量为5的背包。
- 已经有一个2(nums[i]) 的话,有 dp[3]种方法 凑成 容量为5的背包。
- 已经有一个3(nums[i]) 的话,有 dp[2]种方法 凑成 容量为5的背包
- 已经有一个4(nums[i]) 的话,有 dp[1]种方法 凑成 容量为5的背包
- 已经有一个5 (nums[i])的话,有 dp[0]种方法 凑成 容量为5的背包
那么凑整dp[5]有多少方法呢,也就是把 所有的 dp[j - 0nums[i]] 累加起来。
所以求组合类问题的公式,都是类似这种:
dp[j] += dp[j - nums[i]]
3. dp数组如何初始化
背包容量0理解成什么都装不下就是0,理解成只有什么都不装就是1,这里要求的是装法,所以dp[0]初始化为1。
4. 遍历顺序
我们讲过对于01背包问题一维dp的遍历,nums放在外循环,target在内循环,且内循环倒序。
从前nums[i]的数据里取数能填满dp[j]的方法数
完整代码如下:
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int S) {
int sum = 0;
for (int i = 0; i < nums.size(); i++) sum += nums[i];
if (abs(S) > sum) return 0; // 此时没有方案
if ((S + sum) % 2 == 1) return 0; // 此时没有方案
int bagSize = (S + sum) / 2;
vector<int> dp(bagSize + 1, 0);
dp[0] = 1;
for (int i = 0; i < nums.size(); i++) {
for (int j = bagSize; j >= nums[i]; j--) {
dp[j] += dp[j - nums[i]];
}
}
return dp[bagSize];
}
};
这道题的背包的容量有两个维度,不是以前的只有一个维度,因此dp数据应该是二维的了(其实是三维的,如果不是滚动数组的话)这两个维度,一个是m 一个是n,而不同长度的字符串就是不同大小的待装物品。
dp[i][j]:最多有i个0和j个1的strs的最大子集的大小为dp[i][j]。
dp[i][j] 可以由前一个strs里的字符串推导出来,strs里的字符串有zeroNum个0,oneNum个1。
dp[i][j] 就可以是 dp[i - zeroNum][j - oneNum] + 1。
所以递推公式:dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
zeroNumh和oneNum是当前装入的str的0的个数和1的个数类似于01背包的递推公式:dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
因为物品价值不会是负数,初始为0,保证递推的时候dp[i][j]不会被初始值覆盖。
01背包为什么一定是外层for循环遍历物品,内层for循环遍历背包容量且从后向前遍历!
那么本题也是,物品就是strs里的字符串,背包容量就是题目描述中的m和n。
class Solution {
public:
int findMaxForm(vector<string>& strs, int m, int n) {
vector<vector<int>> dp(m + 1, vector<int> (n + 1, 0)); // 默认初始化0
for (string str : strs) { // 遍历物品
int oneNum = 0, zeroNum = 0;
for (char c : str) {
if (c == '0') zeroNum++;
else oneNum++;
}
for (int i = m; i >= zeroNum; i--) { // 遍历背包容量且从后向前遍历!
for (int j = n; j >= oneNum; j--) {
dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
}
}
}
return dp[m][n];
}
};