详解为何能转换为背包问题

简介: 详解为何能转换为背包问题

网络异常,图片无法展示
|


题目描述



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


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


有一堆石头,用整数数组 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
复制代码


示例 3:


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


提示:


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


基本分析



看到标题,心里咯噔了一下 🤣


一般性的石子合并问题通常是只能操作相邻的两个石子,要么是「区间 DP」要么是「四边形不等式」,怎么到 LeetCode 就成了中等难度的题目(也太卷了 🤣


仔细看了一下题目,可对任意石子进行操作,重放回的重量也不是操作石子的总和,而是操作石子的差值。


哦,那没事了 ~ 🤣


也是基于此启发,我们可以这样进行分析。


假设想要得到最优解,我们需要按照如下顺序操作石子:[(sa, sb), (sc, sd), ... ,(si, sj), (sp, sq)][(sa,sb),(sc,sd),...,(si,sj),(sp,sq)]


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


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


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


这意味我们最终得到的结果,可以为原来 stonesstones 数组中的数字添加 +/-+/ 符号,所形成的「计算表达式」所表示。


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


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


什么意思呢?


假设有起始石子 aabb,且两者重量关系为 a \geq bab,那么首先会将 aa 放入「正号堆」,将 bb 放入「负号堆」。重放回操作可以看作产生一个新的重量为 a - bab 的“虚拟石子”,将来这个“虚拟石子”也会参与某次合并操作,也会被添加 +/-+/ 符号:


  • 当对“虚拟石子”添加 ++ 符号,即可 +(a - b)+(ab),展开后为 a - bab,即起始石子 aabb 所在「石子堆」不变
  • 当对“虚拟石子”添加 - 符号,即可 -(a - b)(ab),展开后为 b - aba,即起始石子 aabb 所在「石子堆」交换


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


综上,即使是包含「有放回」操作,最终的结果仍然可以使用「为原来 stonesstones 数组中的数字添加 +/-+/ 符号,形成的“计算表达式”」所表示。


动态规划



有了上述分析后,问题转换为:stonesstones 中的每个数字添加 +/-+/,使得形成的「计算表达式」结果绝对值最小。


(题解)494. 目标和 类似,需要考虑正负号两边时,其实只需要考虑一边就可以了,使用总和 sumsum 减去决策出来的结果,就能得到另外一边的结果。


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


其实就是对「计算表达式」中带 - 的数值提取公因数 -11,进一步转换为两堆石子相减总和,绝对值最小。


这就将问题彻底切换为 01 背包问题:stonesstones 数组中选择,凑成总和不超过 \frac{sum}{2}2sum 的最大价值。


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


整理一下:


定义 f[i][j]f[i][j] 代表考虑前 ii 个物品(数值),凑成总和不超过 jj 的最大价值。


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


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


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


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


代码:


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]);
    }
}
复制代码


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]);
    }
}
复制代码


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(ni=0n1stones[i])
  • 空间复杂度:O(n * \sum_{i = 0}^{n - 1} stones[i])O(ni=0n1stones[i])


最后



这是我们「刷穿 LeetCode」系列文章的第 No.1049 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先将所有不带锁的题目刷完。


在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。


为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:github.com/SharingSour…


在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

相关文章
|
10天前
|
存储 关系型数据库 分布式数据库
PostgreSQL 18 发布,快来 PolarDB 尝鲜!
PostgreSQL 18 发布,PolarDB for PostgreSQL 全面兼容。新版本支持异步I/O、UUIDv7、虚拟生成列、逻辑复制增强及OAuth认证,显著提升性能与安全。PolarDB-PG 18 支持存算分离架构,融合海量弹性存储与极致计算性能,搭配丰富插件生态,为企业提供高效、稳定、灵活的云数据库解决方案,助力企业数字化转型如虎添翼!
|
9天前
|
存储 人工智能 Java
AI 超级智能体全栈项目阶段二:Prompt 优化技巧与学术分析 AI 应用开发实现上下文联系多轮对话
本文讲解 Prompt 基本概念与 10 个优化技巧,结合学术分析 AI 应用的需求分析、设计方案,介绍 Spring AI 中 ChatClient 及 Advisors 的使用。
404 130
AI 超级智能体全栈项目阶段二:Prompt 优化技巧与学术分析 AI 应用开发实现上下文联系多轮对话
|
3天前
|
存储 安全 前端开发
如何将加密和解密函数应用到实际项目中?
如何将加密和解密函数应用到实际项目中?
197 138
|
9天前
|
人工智能 Java API
AI 超级智能体全栈项目阶段一:AI大模型概述、选型、项目初始化以及基于阿里云灵积模型 Qwen-Plus实现模型接入四种方式(SDK/HTTP/SpringAI/langchain4j)
本文介绍AI大模型的核心概念、分类及开发者学习路径,重点讲解如何选择与接入大模型。项目基于Spring Boot,使用阿里云灵积模型(Qwen-Plus),对比SDK、HTTP、Spring AI和LangChain4j四种接入方式,助力开发者高效构建AI应用。
377 122
AI 超级智能体全栈项目阶段一:AI大模型概述、选型、项目初始化以及基于阿里云灵积模型 Qwen-Plus实现模型接入四种方式(SDK/HTTP/SpringAI/langchain4j)
|
3天前
|
存储 JSON 安全
加密和解密函数的具体实现代码
加密和解密函数的具体实现代码
196 136
|
21天前
|
弹性计算 关系型数据库 微服务
基于 Docker 与 Kubernetes(K3s)的微服务:阿里云生产环境扩容实践
在微服务架构中,如何实现“稳定扩容”与“成本可控”是企业面临的核心挑战。本文结合 Python FastAPI 微服务实战,详解如何基于阿里云基础设施,利用 Docker 封装服务、K3s 实现容器编排,构建生产级微服务架构。内容涵盖容器构建、集群部署、自动扩缩容、可观测性等关键环节,适配阿里云资源特性与服务生态,助力企业打造低成本、高可靠、易扩展的微服务解决方案。
1349 8
|
8天前
|
监控 JavaScript Java
基于大模型技术的反欺诈知识问答系统
随着互联网与金融科技发展,网络欺诈频发,构建高效反欺诈平台成为迫切需求。本文基于Java、Vue.js、Spring Boot与MySQL技术,设计实现集欺诈识别、宣传教育、用户互动于一体的反欺诈系统,提升公众防范意识,助力企业合规与用户权益保护。
|
20天前
|
机器学习/深度学习 人工智能 前端开发
通义DeepResearch全面开源!同步分享可落地的高阶Agent构建方法论
通义研究团队开源发布通义 DeepResearch —— 首个在性能上可与 OpenAI DeepResearch 相媲美、并在多项权威基准测试中取得领先表现的全开源 Web Agent。
1460 87