当前位置：首页 > news >正文

【C++动态规划 01背包】1049. 最后一块石头的重量 II|2092

news 2024/11/2 12:55:33

本文涉及知识点

C++动态规划
C++背包问题

LeetCode1049. 最后一块石头的重量 II

有一堆石头，用整数数组 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
提示：
1 <= stones.length <= 30
1 <= stones[i] <= 100

动态规划 01背包

性质一：将石头分成A、B组，如果A组的质量小于B组则交换AB组。每次碰撞都从AB组各取一个碰撞，碰撞剩余的石头归还原组。碰撞后剩余石头的质量一定为x= $\sum(a)-\sum(b)$ 。每次碰撞AB组都减少相同的质量，直到B组的质量为0。
性质二：x > max(a)，则最优一定剩余2块或更多石头。石头质量不会增加，故块石头的质量一定小于等于max(a)。
性质三：x <= max(a)，则一定能剩余0或1块石头。从a组取出max(a)后ab组碰撞，b组剩余[0,max(a)]和max(a）碰撞。
性质四：会不会某块石头，某次碰撞后，从A组移动B组？会，但无需枚举。
不失一般性，这块石头是由a,b,c,d碰撞成的，在碰撞前将a,b,c,d换组效果完全一样。
性质二的情况无需手动排除，会被更优方案淘汰，比如：将max(a)移到b组。

动态规划的状态表示

dp[i][s] 表示，从前i块石头中选择若干石头总重量为s的方案是否存在。空间复杂度：O(nS) ,S是a之和。

动态规划的转移方程

枚举前置状态
dp[i+1] = dp[i] 不选择第i块石头
dp[i+1][s+nums[i]] ||= dp[i][s] 选择第i块石头

动态规程的初始值

dp[0][0]=true。

动态规划的填报顺序

i = 0 To n-1 sum = 0 To S-nums[i]

动态规划的返回值

dp.back()[s] 为true。
min(bas(S-2s))

代码

核心代码

class Solution {public:int lastStoneWeightII(vector<int>& stones) {const int N = stones.size();const auto& S = accumulate(stones.begin(), stones.end(),0);vector<vector<bool>> dp(N + 1, vector<bool>(S + 1));dp[0][0] = true;for (int i = 0; i < N; i++) {dp[i + 1] = dp[i];for (int s = 0; s + stones[i] <= S; s++) {if (!dp[i][s])continue;dp[i + 1][s + stones[i]] = true;}}int iMin = INT_MAX;for (int s = 0; s <= S; s++) {if (!dp.back()[s])continue;iMin = min(iMin, abs(S - 2 * s));}return iMin;}};

单元测试

vector<int> stones;TEST_METHOD(TestMethod1){stones = { 2, 7, 4, 1, 8, 1 };auto res = Solution().lastStoneWeightII(stones);AssertEx(1, res);}TEST_METHOD(TestMethod12){stones = { 31,26,33,21,40};auto res = Solution().lastStoneWeightII(stones);AssertEx(5, res);}

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标及时的反馈拉伸区（难度合适）专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功成功+反思=成功