【蓝桥杯速成】| 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 <= 200
• 1 <= 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) {//简化想法：不要被困在题目两两相撞的逻辑中//如果就两块石头，那么相撞结果肯定就是差值//那么我们何不把这么多块石头就分成两组，要是两组大小相等那最小重量肯定为0int 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;}
};