LeetCode-Day43——背包问题实战
416. 分割等和子集
给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
注意:
每个数组中的元素不会超过 100
数组的大小不会超过 200
示例 1:
1
2
3
| 输入: [1, 5, 11, 5]
输出: true
解释: 数组可以分割成 [1, 5, 5] 和 [11].
|
示例 2:
1
2
3
| 输入: [1, 2, 3, 5]
输出: false
解释: 数组不能分割成两个元素和相等的子集.
|
思路：
这就是一个01背包准确值的问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public:
bool canPartition(vector<int>& nums) {
int sum = 0;
for(int i = 0;i < nums.size();i++) {
sum += nums[i];
}
if(sum % 2 != 0) {
return false;
}
int target = sum / 2;
vector<int> dp(target + 1, INT_MIN);
dp[0] = 0;
for(int num : nums) {
for(int i = target;i >= num;i--) {
dp[i] = max(dp[i], dp[i - num] + num);
dp[i] = dp[i] < 0 ? INT_MIN : dp[i];
}
}
return dp[target] == target;
}
};
|
494. 目标和
给定一个非负整数数组，a1, a2, …, an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。
返回可以使最终数组和为目标数 S 的所有添加符号的方法数。
示例 1:
1
2
3
4
5
6
7
8
9
10
11
| 输入: 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背包问题，假设取加号部分的和为x，取减号部分的和为y，则有
x + y = sum(nums)
x - y = S
则直接可以求解 x = (sum + S) / 2
所以这道题本质上就是在问你，从这些数当中取出哪些数，可以让和为x，这样我们就将问题转换为01背包问题了
上Code：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public:
int findTargetSumWays(vector<int>& nums, int S) {
int sum = 0;
for(int num : nums) {
sum += num;
}
if(sum < S || (sum + S) % 2 != 0) {
return 0;
}
int target = (sum + S) / 2;
vector<long long> dp(target + 1, 0);
dp[0] = 1;
for(int num : nums) {
for(int i = target;i >= num;i--) {
dp[i] += dp[i - num];
}
}
return dp[target];
}
};
|
这里需要注意一件事情，就是这里的dp数组表示的是方法的种数。
474. 一和零
在计算机界中，我们总是追求用有限的资源获取最大的收益。
现在，假设你分别支配着 m 个 0 和 n 个 1。另外，还有一个仅包含 0 和 1 字符串的数组。
你的任务是使用给定的 m 个 0 和 n 个 1 ，找到能拼出存在于数组中的字符串的最大数量。每个 0 和 1 至多被使用一次。
注意:
给定 0 和 1 的数量都不会超过 100。
给定字符串数组的长度不会超过 600。
示例 1:
1
2
3
| 输入: Array = {"10", "0001", "111001", "1", "0"}, m = 5, n = 3
输出: 4
解释: 总共 4 个字符串可以通过 5 个 0 和 3 个 1 拼出，即 "10","0001","1","0" 。
|
示例 2:
1
2
3
| 输入: Array = {"10", "0", "1"}, m = 1, n = 1
输出: 2
解释: 你可以拼出 "10"，但之后就没有剩余数字了。更好的选择是拼出 "0" 和 "1" 。
|
思路：
就把这个问题想象成有两个约束条件的多维背包问题，状态转换方程为：
f[i, u, v] = max(f[i - 1, u, v], f[u - 1][u - Di][v - Ci] + Wi)
然后优化空间和时间的方法，就是变成二维数组，加上倒着遍历！
上Code：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class Solution {
public:
pair<int, int> countZO(string str) {
pair<int, int> ans(0, 0);
for(char c : str) {
if(c == '0') {
ans.first++;
} else {
ans.second++;
}
}
return ans;
}
int findMaxForm(vector<string>& strs, int m, int n) {
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
for(string str : strs) {
pair<int, int> zo = countZO(str);
for(int i = m;i >= zo.first;i--) {
for(int j = n;j >= zo.second;j--) {
dp[i][j] = max(dp[i][j], dp[i - zo.first][j - zo.second] + 1);
}
}
}
return dp[m][n];
}
};
|