01背包问题
这个问题之前有讲到过，可以参考动态规划01背包问题
此次主要讲述01背包问题下的拓展出来的一些问题。
题目一、分割等和子集
题目链接：leetcode416.分割等和子集
给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
注意:
每个数组中的元素不会超过 100
数组的大小不会超过 200
- 1
- 2
- 3
示例 1:
输入: [1, 5, 11, 5]
输出: true
解释: 数组可以分割成 [1, 5, 5] 和 [11].
- 1
- 2
- 3
- 4
- 5
示例 2:
输入: [1, 2, 3, 5]
输出: false
解释: 数组不能分割成两个元素和相等的子集.
- 1
- 2
- 3
- 4
- 5
这种题乍一眼看到感觉无从下手，其实不然。
思路
1.首先思考一下，既然要将它们分为相等的两份，那么他们的和必然是偶数，否则必定不会被分成相等的两份。
2.这个问题如何转换为01背包问题呢，其实很简单，首先确定什么是背包的容量，什么是物品的容量，什么又是物品的价值。
数组中的所有的数的和我们是可以求出来的，那么排除它是偶数后，它的一半也是能算出来的，也就是说，如果我用数组中这些数能得到总和的一半，那么就表示我一定有一种方法可以把它分为相等的两份。
假设数组所有数的和为偶数并记为sum，那么它的一半记为half_sum，那么它就是背包的容量。而整个数组既是物品的重量，也是物品的价值。
那么这道题就可以理解为，再容量为half_sum的大小下，我能装入的最大的物品价值是多少。
求出这个最优解后，只需要和half_sum比较是否相等即可。
递推公式
创建dp数组，用i表示物品数，j表示当前容量，dp[j]表示j容量下的最大总和。
初始化为0，因为只要当前总和为0，那么我总是可以获取到比0大的总和。
dp[j] = max(dp[j]，dp[j - nums[i]] + nums[i])
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 == 1) return false;
//获得总和的一半，也是背包的容量
int half_sum = sum/2;
vector<int> dp(half_sum + 1,0);
for(int i = 0;i<nums.size();i++)
{
for(int j = half_sum;j>=nums[i];j--)
{
dp[j] = max(dp[j],dp[j - nums[i]] + nums[i]);
}
}
return dp[half_sum] == half_sum;
}
};
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
题目二、最后一块石头的重量 II
题目链接：最后一块石头的重量 II
有一堆石头，每块石头的重量都是正整数。
每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
如果 x == y，那么两块石头都会被完全粉碎；
如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
最后，最多只会剩下一块石头。返回此石头最小的可能重量。如果没有石头剩下，就返回 0。
- 1
- 2
- 3
- 4
示例：
输入：[2,7,4,1,8,1]
输出：1
解释：
组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]，
组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]，
组合 2 和 1，得到 1，所以数组转化为 [1,1,1]，
组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。
- 1
- 2
- 3
- 4
- 5
- 6
- 7
提示：
1 <= stones.length <= 30
1 <= stones[i] <= 1000
- 1
- 2
思路
1.同样想要用01背包问题的思想解决这个问题，那么就得要先明确背包容量，物品重量和物品价值，我想要得到最小的石头重量，那么我只需要将这一堆石头分为重量最接近的两份就可以了，这样粉碎下来，一定能得到最小的石头的重量。
2.分析出来问题的本质后，就往01背包上靠拢，首先确定背包的最大容量，同样的，我们将所有石头的总质量加起来，除以二就是背包的容量，注意，这里不需要判断是否为奇数，因为只需要将这一堆石头分为重量最接近的两堆，可以相等，也可以不相等。
3.同样，石头的重量既代表重量也代表它的价值。
递推公式
创建dp数组，用i表示物品数，j表示当前容量，dp[j]表示j容量下的最大总和。
初始化为0，因为只要当前最大质量和和为0，那么我总是可以获取到比0大的质量总和。
dp[j] = max(dp[j]，stonesdp[j - [i]] + stones[i])
class Solution {
public:
int lastStoneWeightII(vector<int>& stones) {
int sum = 0,half_sum = 0;;
for(int i = 0;i<stones.size();i++)
{
sum+=stones[i];
}
half_sum = sum/2;
vector<int> dp(half_sum + 1,0);
for(int i = 0;i<stones.size();i++)
{
for(int j = half_sum;j>=stones[i];j--)
{
dp[j] = max(dp[j],dp[j - stones[i]] + stones[i]);
}
}
//因为half_sum是sum/2向下取整的，所以sum - dp[half_sum]一定大于等于dp[half_sum]的
return sum - 2*dp[half_sum];
}
};
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
题目三、目标和
题目链接：目标和
给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。
返回可以使最终数组和为目标数 S 的所有添加符号的方法数。
- 1
- 2
- 3
示例：
输入：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。
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
提示：
数组非空，且长度不会超过 20 。
初始的数组的和不会超过 1000 。
保证返回的最终结果能被 32 位整数存下。
- 1
- 2
- 3
这道题曾是我面试腾讯时的一道题，当时没做出来，下来结合大佬的思路自己想了想，总结出来。
首先大家肯定想到的是回溯法来解决这个问题，但是如果这个数组的长度特别的长，那么很容易超出时间复杂度。将这道题本质看出来，实则还是一道01背包的问题。
思路
首先，定义一下这些数的总和为sum，要得到目标数S，那么一定有从sum中拆出来两个数记为所有添加+号得和left_sum，所有添加-号得和为right_sum，则有：
left_sum - right_sum = S
而left_sum + right_sum = sum
则就推出：left_sum = (sum + S)/2
这里要注意一下：left_sum ，right_sum ,sum，S都是确定的，因此(sum + S)/2不能让它向下取整，即sum+S必须为偶数，否则没有方法能够得到目标数
因为sum是固定的，S也是固定的，那么就转换为求数组中能得到left_sum得总和。
定义dp数组，i表示当前数的下标，j表示当前容量，dp[j]表示能得到数字和为j得所有方法数。
则有：dp[j] +=dp[j - nums[i]]
例如：假设nums[i] = 2，我现在想要求当前情况下总和为5的方法总数，那么除了我已知的能获得5的方法总和外，我还需要直到dp[5 - 2]的方法总和，因为我知道dp[3]的方法数，那么dp[3]的方法数就是dp[5]的方法数，所以给dp[5]加上即可。
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(sum < S || (sum + S) % 2 == 1) return 0;
int left_sum = (S + sum) / 2;
vector<int> dp(size + 1,0);
dp[0] = 1;
for(int i = 0;i<nums.size();i++)
{
for(int j = left_sum;j>=nums[i];j--)
{
dp[j] += dp[j - nums[i]];
}
}
return dp[left_sum];
}
};
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23