前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >【动态规划/背包问题】加餐一道「01 背包」变形题

【动态规划/背包问题】加餐一道「01 背包」变形题

作者头像
宫水三叶的刷题日记
发布2021-10-20 16:17:52
9470
发布2021-10-20 16:17:52
举报

前言

今天是我们讲解「动态规划专题」中的「背包问题」的第二十一篇

今天将加餐/补充一道「01 背包」的题目。

另外,我在文章结尾处列举了我所整理的关于背包问题的相关题目。

背包问题我会按照编排好的顺序进行讲解(每隔几天更新一篇,确保大家消化)。

你可以先尝试做做,也欢迎你向我留言补充,你觉得与背包相关的 DP 类型题目 ~

题目描述

这是 LeetCode 上的「1049. 最后一块石头的重量 II」,难度为「中等」

Tag : 「动态规划」、「背包问题」、「01 背包」、「数学」

有一堆石头,用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。

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

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

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

示例 1:

代码语言:javascript
复制
输入: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:

代码语言:javascript
复制
输入:stones = [31,26,33,21,40]
输出:5

示例 3:

代码语言:javascript
复制
输入:stones = [1,2]
输出:1

提示:

  • 1 <= stones.length <= 30
  • 1 <= stones[i] <= 100

基本分析

根据题意:可对任意石子进行操作,重放回的重量也不是操作石子的总和,而是操作石子的差值。

基于此,我们可以这样进行分析。

假设想要得到最优解,我们需要按照如下顺序操作石子:

[(sa, sb), (sc, sd), ... ,(si, sj), (sp, sq)]

其中

abcdijpq

代表了石子编号,字母顺序不代表编号的大小关系

如果不考虑「有放回」的操作的话,我们可以划分为两个石子堆(正号堆/负号堆):

  • 将每次操作中「重量较大」的石子放到「正号堆」,代表在这次操作中该石子重量在「最终运算结果」中应用
+

运算符

  • 将每次操作中「重量较少/相等」的石子放到「负号堆」,代表在这次操作中该石子重量在「最终运算结果」中应用
-

运算符

这意味我们最终得到的结果,可以为原来

stones

数组中的数字添加

+/-

符号,所形成的「计算表达式」所表示。

那有放回的石子重量如何考虑?

其实所谓的「有放回」操作,只是触发调整「某个原有石子」所在「哪个堆」中,并不会真正意义上的产生「新的石子重量」。

什么意思呢?

假设有起始石子

a

b

,且两者重量关系为

a \geq b

,那么首先会将

a

放入「正号堆」,将

b

放入「负号堆」。重放回操作可以看作产生一个新的重量为

a - b

的“虚拟石子”,将来这个“虚拟石子”也会参与某次合并操作,也会被添加

+/-

符号:

  • 当对“虚拟石子”添加
+

符号,即可

+(a - b)

,展开后为

a - b

,即起始石子

a

b

所在「石子堆」不变

  • 当对“虚拟石子”添加
-

符号,即可

-(a - b)

,展开后为

b - a

,即起始石子

a

b

所在「石子堆」交换

因此所谓不断「合并」&「重放」,本质只是在构造一个折叠的计算表达式,最终都能展开扁平化为非折叠的计算表达式。

综上,即使是包含「有放回」操作,最终的结果仍然可以使用「为原来

stones

数组中的数字添加

+/-

符号,形成的“计算表达式”」所表示。

动态规划

有了上述分析后,问题转换为:

stones

中的每个数字添加

+/-

,使得形成的「计算表达式」结果绝对值最小。

494. 目标和 类似,需要考虑正负号两边时,其实只需要考虑一边就可以了,使用总和

sum

减去决策出来的结果,就能得到另外一边的结果。

同时,由于想要「计算表达式」结果绝对值,因此我们需要将石子划分为差值最小的两个堆。

其实就是对「计算表达式」中带

-

的数值提取公因数

-1

,进一步转换为两堆石子相减总和,绝对值最小。

这就将问题彻底切换为 01 背包问题:

stones

数组中选择,凑成总和不超过

\frac{sum}{2}

的最大价值。

其中「成本」&「价值」均为数值本身。

整理一下:

定义

f[i][j]

代表考虑前

i

个物品(数值),凑成总和不超过

j

的最大价值。

每个物品都有「选」和「不选」两种决策,转移方程为:

f[i][j] = \max(f[i - 1][j], f[i - 1][j - stones[i - 1]] + stones[i - 1])

与完全背包不同,01 背包的几种空间优化是不存在时间复杂度上的优化,因此写成 朴素二维、滚动数组、一维优化 都可以。

建议直接上手写「一维空间优化」版本,是其他背包问题的基础。

代码:

代码语言:javascript
复制
class Solution {
    public int lastStoneWeightII(int[] ss) {
        int n = ss.length;
        int sum = 0;
        for (int i : ss) sum += i;
        int t = sum / 2;
        int[][] f = new int[n + 1][t + 1];
        for (int i = 1; i <= n; i++) {
            int x = ss[i - 1];
            for (int j = 0; j <= t; j++) {
                f[i][j] = f[i - 1][j];
                if (j >= x) f[i][j] = Math.max(f[i][j], f[i - 1][j - x] + x);
            }
        }
        return Math.abs(sum - f[n][t] - f[n][t]);
    }
}
代码语言:javascript
复制
class Solution {
    public int lastStoneWeightII(int[] ss) {
        int n = ss.length;
        int sum = 0;
        for (int i : ss) sum += i;
        int t = sum / 2;
        int[][] f = new int[2][t + 1];
        for (int i = 1; i <= n; i++) {
            int x = ss[i - 1];
            int a = i & 1, b = (i - 1) & 1;
            for (int j = 0; j <= t; j++) {
                f[a][j] = f[b][j];
                if (j >= x) f[a][j] = Math.max(f[a][j], f[b][j - x] + x);
            }
        }
        return Math.abs(sum - f[n&1][t] - f[n&1][t]);
    }
}
代码语言:javascript
复制
class Solution {
    public int lastStoneWeightII(int[] ss) {
        int n = ss.length;
        int sum = 0;
        for (int i : ss) sum += i;
        int t = sum / 2;
        int[] f = new int[t + 1];
        for (int i = 1; i <= n; i++) {
            int x = ss[i - 1];
            for (int j = t; j >= x; j--) {
                f[j] = Math.max(f[j], f[j - x] + x);
            }
        }
        return Math.abs(sum - f[t] - f[t]);
    }
}
  • 时间复杂度:
O(n * \sum_{i = 0}^{n - 1} stones[i])
  • 空间复杂度:
O(n * \sum_{i = 0}^{n - 1} stones[i])

背包问题(目录)

  1. 01背包 : 背包问题 第一讲
    1. 【练习】01背包 : 背包问题 第二讲
    2. 【学习&练习】01背包 : 背包问题 第三讲
    3. 【加餐/补充】01 背包: 本篇
  2. 完全背包 : 背包问题 第四讲
    1. 【练习】完全背包 : 背包问题 第五讲
    2. 【练习】完全背包 : 背包问题 第六讲
    3. 【练习】完全背包 : 背包问题 第七讲
  3. 多重背包 : 背包问题 第八讲
  4. 多重背包(优化篇)
    1. 【上】多重背包(优化篇): 背包问题 第九讲
    2. 【下】多重背包(优化篇): 背包问题 第十讲
  5. 混合背包 : 背包问题 第十一讲
  6. 分组背包 : 背包问题 第十二讲
    1. 【练习】分组背包 : 背包问题 第十三讲
  7. 多维背包
    1. 【练习】多维背包 : 背包问题 第十四讲
    2. 【练习】多维背包 : 背包问题 第十五讲
  8. 树形背包 : 背包问题 第十六讲
    1. 【练习篇】树形背包 : 背包问题 第十七讲
    2. 【练习篇】树形背包 : 背包问题 第十八讲
  9. 背包求方案数
    1. 【练习】背包求方案数 : 背包问题 第十九讲
    2. 【练习】背包求方案数 : 背包问题 第十五讲

[注:因为之前实在找不到题,这道「求方案数」题作为“特殊”的「多维费用背包问题求方案数」讲过]

  1. 背包求具体方案
    1. 【练习】背包求具体方案 : 背包问题 第二十讲
    2. 【练习】背包求具体方案
  2. 泛化背包
    1. 【练习】泛化背包
本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2021-10-11,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 宫水三叶的刷题日记 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 前言
  • 题目描述
  • 基本分析
  • 动态规划
  • 背包问题(目录)
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档