【算法与数据结构】1049、LeetCode 最后一块石头的重量 II

这篇具有很好参考价值的文章主要介绍了【算法与数据结构】1049、LeetCode 最后一块石头的重量 II。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。

一、题目

【算法与数据结构】1049、LeetCode 最后一块石头的重量 II,算法,算法

二、解法

  思路分析:本题需要得到石头之间两两粉碎之后的最小值,那么一个简单的思路就是将这堆石头划分成大小相近的两小堆石头,然后粉碎,这样得到的结果必然是最优值。那么如何划分呢?我们可以将所有石头的质量求和,假设和为 s u m sum sum,以 s u m / 2 sum/2 sum/2为界限。一堆石头质量设为 w 1 w_1 w1,有 w 1 ≤ s u m / 2 w_1 \leq sum/2 w1sum/2;而另外一堆石头质量 w 2 w_2 w2,有 w 2 ≥ s u m / 2 w_2 \geq sum/2 w2sum/2,且 w 1 + w 2 = s u m w_1 + w_2=sum w1+w2=sum因为要求两堆石头粉碎之后的质量 Δ \Delta Δ最小,所以划分出来的两堆石头重量越接近越好,等同于 w 1 w_1 w1 w 2 w_2 w2越接近于 s u m / 2 sum/2 sum/2。所以我们可以将 m i n ( Δ = w 2 − w 1 ) min(\Delta =w_2- w_1) min(Δ=w2w1)问题,转化为 m a x ( w 1 ) , s . t . w 1 ≤ s u m / 2 max(w_1), s.t. w_1 \leq sum/2 max(w1),s.t.w1sum/2,即在这个数组中找到和最接近sum/2的子集。这是一个01背包问题。最终的最小质量 Δ m i n = w 2 − w 1 = s u m − 2 ∗ w 1 \Delta_{min}= w_2- w_1 = sum - 2*w_1 Δmin=w2w1=sum2w1
  程序如下

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int sum = accumulate(stones.begin(), stones.end(), 0);
        vector<int> dp(vector<int>(sum/2 + 1, 0));
        for (int i = 0; i < stones.size(); i++) {			// 遍历物品
            for (int j = sum/2; j >= stones[i]; j--) {			// 遍历背包容量
                dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
            }
        }
        return sum -2 * dp[sum/2];
    }
};

复杂度分析:

  • 时间复杂度: O ( n 2 ) O(n^2) O(n2)
  • 空间复杂度: O ( n ) O(n) O(n)

三、完整代码

# include <iostream>
# include <vector>
# include <numeric>
# include <algorithm>
using namespace std;

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int sum = accumulate(stones.begin(), stones.end(), 0);
        vector<int> dp(vector<int>(sum/2 + 1, 0));
        for (int i = 0; i < stones.size(); i++) {			// 遍历物品
            for (int j = sum/2; j >= stones[i]; j--) {			// 遍历背包容量
                dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
            }
        }
        return sum -2 * dp[sum/2];
    }
};

int main() {
    Solution s1;
    vector<int> stones = { 2,7,4,1,8,1 };
    int result = s1.lastStoneWeightII(stones);
    cout << result << endl;
    system("pause");
    return 0;
}

end文章来源地址https://www.toymoban.com/news/detail-811058.html

到了这里,关于【算法与数据结构】1049、LeetCode 最后一块石头的重量 II的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • ( 背包问题) 1049. 最后一块石头的重量 II ——【Leetcode每日一题】

    难度:中等 有一堆石头,用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。 每一回合,从中选出 任意两块石头 ,然后将它们一起粉碎。假设石头的重量分别为 x 和 y ,且 x = y 。那么粉碎的可能结果如下: 如果 x == y ,那么两块石头都会被完全粉碎; 如果 x !=

    2024年02月08日
    浏览(51)
  • Day43|leetcode 1049.最后一块石头的重量II、494.目标和、474.一和零

    题目链接:1049. 最后一块石头的重量 II - 力扣(LeetCode) 视频链接:动态规划之背包问题,这个背包最多能装多少?LeetCode:1049.最后一块石头的重量II_哔哩哔哩_bilibili 有一堆石头,每块石头的重量都是正整数。 每一回合,从中选出任意两块石头,然后将它们一起粉碎。假设

    2024年02月10日
    浏览(51)
  • [Leetcode] 416. 分割等和子集、1049. 最后一块石头的重量 II、494. 目标和、474. 一和零

    内容:今天复习下dp数组中的背包问题 分割等和子集 - 能否装满 最后一块石头 - 尽可能装满 目标和 - 有多少种方法装 一和零 - 装满背包有多少个物品 416. 分割等和子集 10背包:用/不用;有容量;有价值 dp[j] : 容量为j,最大价值为dp[j]         重量和价值等价 dp[target] == t

    2024年02月16日
    浏览(42)
  • 算法训练第四十三天|1049. 最后一块石头的重量 II 、494. 目标和、474.一和零

    题目链接:1049. 最后一块石头的重量 II 参考:https://programmercarl.com/1049.%E6%9C%80%E5%90%8E%E4%B8%80%E5%9D%97%E7%9F%B3%E5%A4%B4%E7%9A%84%E9%87%8D%E9%87%8FII.html 题目难度:中等 有一堆石头,每块石头的重量都是正整数。 每一回合,从中选出任意两块石头,然后将它们一起粉碎。假设石头的重量分

    2023年04月09日
    浏览(37)
  • 【LeetCode题目详解】第九章 动态规划 part05 1049. 最后一块石头的重量 II 494. 目标和 474.一和零(day43补)

    有一堆石头,用整数数组  stones 表示。其中  stones[i] 表示第 i 块石头的重量。 每一回合,从中选出 任意两块石头 ,然后将它们一起粉碎。假设石头的重量分别为  x 和  y ,且  x = y 。那么粉碎的可能结果如下: 如果  x == y ,那么两块石头都会被完全粉碎; 如果  x != y

    2024年02月09日
    浏览(38)
  • 代码随想录Day36 动态规划05 LeetCode T1049最后一块石头的重量II T494 目标和 T474 一和零

    理论基础  : 代码随想录Day34 LeetCode T343整数拆分 T96 不同的二叉搜索树-CSDN博客 1.明白dp数组的含义 2.明白递推公式的含义 3.初始化dp数组 4.注意dp数组的遍历顺序 5.打印dp数组排错 题目链接:1049. 最后一块石头的重量 II - 力扣(LeetCode) 这题我们仍然采用动规五部曲来写,这题和

    2024年02月06日
    浏览(41)
  • Leet code1049 最后一块石头的重量II

    1049 最后一块石头的重量II 【问题描述】 有一堆石头,用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。 每一回合,从中选出 任意两块石头 ,然后将它们一起粉碎。假设石头的重量分别为 x 和 y ,且 x = y 。那么粉碎的可能结果如下: 如果 x == y ,那么两块石头

    2024年02月13日
    浏览(44)
  • 力扣第1049题 最后一块石头的重量Il c++ 动态规划(01背包)

    1049. 最后一块石头的重量 II 中等 相关标签 有一堆石头,用整数数组  stones  表示。其中  stones[i]  表示第  i  块石头的重量。 每一回合,从中选出 任意两块石头 ,然后将它们一起粉碎。假设石头的重量分别为  x  和  y ,且  x = y 。那么粉碎的可能结果如下: 如果  x

    2024年02月06日
    浏览(45)
  • day43 | 1049. 最后一块石头的重量 II、494. 目标和、474.一和零

    目录: 1049. 最后一块石头的重量 II 有一堆石头,用整数数组  stones  表示。其中  stones[i]  表示第  i  块石头的重量。 每一回合,从中选出 任意两块石头 ,然后将它们一起粉碎。假设石头的重量分别为  x  和  y ,且  x = y 。那么粉碎的可能结果如下: 如果  x == y ,那

    2024年02月12日
    浏览(34)
  • Day43|动态规划part05: 1049. 最后一块石头的重量 II、494. 目标和、474. 一和零

    本题物品的重量为stones[i],物品的价值也为stones[i]。 对应着01背包里的物品重量weight[i]和 物品价值value[i]。 确定dp数组以及下标的含义 dp[j]表示容量(这里说容量更形象,其实就是重量)为j的背包,最多可以背最大重量为dp[j] 。 确定递推公式 01背包的递推公式为:dp[j] = ma

    2024年04月23日
    浏览(48)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包