动态规划06-最后一块石头的重量

发布时间:2023年12月26日

题目描述

有一堆石头,每块石头的重量都是正整数。

每一回合,从中选出任意两块石头,然后将它们一起粉碎。假设石头的重量分别为 x 和 y,且 x <= y。那么粉碎的可能结果如下:

如果 x == y,那么两块石头都会被完全粉碎;

如果 x != y,那么重量为 x 的石头将会完全粉碎,而重量为 y 的石头新重量为 y-x。

最后,最多只会剩下一块石头。返回此石头最小的可能重量。如果没有石头剩下,就返回 0。

思路分析

本题的情况就是不断寻找重量最接近的石头,然后最好能够实现石头的消去。最优的情况就是石头消去以后的重量为零,这样一讲,好像就能够跟划分相等子集结合起来了。将集合分成值相等的两个部分,最终得到的就是0,

  1. 定义dp[j]的含义:当背包的容量为j的时候,最大的石头的价值是dp[j],本题情况下的背包容量就是石头总重量的一半。
  2. 确定迭代条件:dp[j] = Max(dp[j-1], dp[j-stone[i]]+stone[i]),翻译一下就是是否选择当前的石头,以及对实时价值的评判。
  3. 初始化dp数组:由于初始状态什么都还不知道,所以将dp[]数组全部设置成0。
  4. 确定遍历顺序:外层循环遍历物品,采用顺序遍历;内层循环遍历背包,采用倒序遍历。
  5. 代入数据验证。

代码展示

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        vector<int> dp(15001, 0);
        int sum = 0;
        for (int i = 0; i < stones.size(); i++) sum += stones[i];
        int target = sum / 2;
        for (int i = 0; i < stones.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] - dp[target];
    }
};
文章来源:https://blog.csdn.net/weixin_73074012/article/details/135232763
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。