【蓝桥杯速成】| 7.01背包练习生
题目一：分割等和子集
问题描述
416. 分割等和子集 - 力扣（LeetCode）
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
示例 1：
输入：nums = [1,5,11,5] 输出：true 解释：数组可以分割成 [1, 5, 5] 和 [11] 。
示例 2：
输入：nums = [1,2,3,5] 输出：false 解释：数组不能分割成两个元素和相等的子集。
提示：
1 <= nums.length <= 2001 <= nums[i] <= 100
解题步骤
在昨天的01背包理论学习结束后，对于这个题目我们可以照葫芦画瓢地浅套一下
之前的题目物品有序号，价值，重量3个属性，本题就只有序号和数值两个属性，
为了便于理解其实我们可以将这个nums的值既视为这个数字的价值，也视为这个数字的重量
背包的容量就是我们要寻求的目标值
为了将数组分割成两个元素和相等的子集，
我一开始想的是：总和-当前值=之前值
这一看就涉及很多，何不再想简单一点，要能分成一半一半，
那目标target就定为一半不就好了，如果有刚好和是一半的，那剩下的肯定是另一半（有点绕但应该能理解）
那么很明显这里可以做个剪枝，如果数组之和为奇数，那必然找不到等分的！
if(sum% 2==1) return false;
ok，走流程！
这里选择更优的一维数组来实现
1.确定dp数组的定义
参考之前的题目，我们将dp[ j ]理解为背包容量为 j 时所取的和最大值
最后我们要求的就是dp[ target ]
如果dp[ target ]=target，就是用目标容量装下了目标价值的数，符合题意返回true
否则返回false
那么数组大小就可以设置为target+1;
vecto<int> dp(target+1);
2.确定递推公式
还是需要使用max函数，在滚动状态中选择最大值
dp[ j ]=max( dp[ j ] ,dp[ j -nums[i]]+nums[i])//前一个nums[i]表示这个数字占的位置，后一个表示这个数字的价值
3.初始化
没有什么需要特别初始化为具体值的，明确dp[ 0 ]=0(背包容量为0价值必为0)
其它值只要不影响取最大值即可，推荐统一初始化为0
4.遍历顺序
按照昨天的推理，我们用外层遍历数字，用内层倒序遍历背包容量，
这样可以在确保每个数字只使用一次的同时
可以顺利的利用之前的dp值推理出现在的dp值
for(int i=0;i<nums.size();i++){
for(int j=target;j<=nums[i];j--){
最后对结果做判断
if (dp[target]==target) return true;
完整代码如下👇
code
class Solution {
public:
bool canPartition(vector<int>& nums) {
int n=nums.size();
if(accumulate(nums.begin(), nums.end(),0)%2==1) return false;//和为奇数是凑不出来滴！
int target=accumulate(nums.begin(), nums.end(), 0)/2;
vector<int> dp(target+1,0);
//背包容量为这个数组所有值之和的一半，
//设为总和你不还得减一下再比较，那你不如直接以一半为目标
//i表示可选范围在前i个数字
//dp[j]表示背包容量为j时的各种组合中的最大和（奔着一半去的嘛）
for(int i=0;i<n;i++){
for(int j=target;j>=nums[i];j--){
dp[j]=max(dp[j],dp[j-nums[i]]+nums[i]);//nums的值既是价值也是质量
}
}
if(dp[target]==target)
return true;
return false;
}
};题目二：最后一块石头的重量
问题描述
1049. 最后一块石头的重量 II - 力扣（LeetCode）
有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。
每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
- 如果
x == y，那么两块石头都会被完全粉碎； - 如果
x != y，那么重量为x的石头将会完全粉碎，而重量为y的石头新重量为y-x。
最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。
示例 1：
输入：stones = [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]，这就是最优值。
示例 2：
输入：stones = [31,26,33,21,40] 输出：5
解题步骤
一开始，看完题目我的想法就被困在了对对碰中，
一个劲地想怎么在最后取到min？怎么任选？
但是跳出仍选石头，进行碰撞，更新石头值这个循环
应该可以悟到，我们能把这个任务简化为两个大石头之间的较量
倘若两个大石头的值相等，那最后就是被消消乐完了，最小值为0
不相等也没关系，趋近相等就可以得出最小差值
这么一想，这个题目就和上面的分割等和子集一样了
就是目标判定的时候我们不需要它就和target相等
所以稍微修改一下代码逻辑就可以AC啦
开始先计算一下几个有关量
int size=stones.size();//遍历石头的边界
int sum=accumulate(stones.begin(),stones.end(),0);//石头总和
int target=sum/2;//尽可能取到的，理想化的目标
因为我们不再要求等分，所以对%2的判断也不再需要
再定义dp数组，同时全部初始化为0
vector<int> dp(target+1,0);
然后是循环体和递推公式，依旧是逆推，每次取最大值
for(int i=0;i<size;i++){
for(int j=target;j>=stones[i];j--){
dp[j]=max(dp[j],dp[j-stones[i]]+stones[i]);
}
}
最后再明确一下目标，凑出最趋近于石头总和一半的结果，
一组石头的总和为dp[target]，那另一组就是sum-dp[target]
最后两组差值就是sum-dp[target]*2
return sum-dp[target]*2;
code
class Solution {
public:
int lastStoneWeightII(vector<int>& stones) {
//简化想法：不要被困在题目两两相撞的逻辑中
//如果就两块石头，那么相撞结果肯定就是差值
//那么我们何不把这么多块石头就分成两组，要是两组大小相等那最小重量肯定为0
int size=stones.size();
int sum=accumulate(stones.begin(),stones.end(),0);
int target=sum/2;//尽可能取到
vector<int> dp(target+1,0);
for(int i=0;i<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]*2;
}
};