算法练习-01背包问题【含递推公式推导】(思路+流程图+代码)

难度参考

        难度:困难

        分类:动态规划

        难度与分类由我所参与的培训课程提供,但需 要注意的是,难度与分类仅供参考。且所在课程未提供测试平台,故实现代码主要为自行测试的那种,以下内容均为个人笔记,旨在督促自己认真学习。

题目

        动态规划经典问题01背包?

        具体内容:

        背包最大重量为4

        物品如下:

重量价值
物品0115
物品1320
物品2430

        问背包能背的最大重量是多少?

思路

        0-1 背包问题的动态规划解法基于以下思路:

  1. 子问题定义

    • 将原问题分解为子问题。在这里,我们考虑"对于给定的背包容量和一组物品,最大价值是多少?"
    • 定义状态 dp[i][w] —— 表示考虑前 i 个物品时,对于不超过 w 重量的背包,所能得到的最大价值。
  2. 初始条件

    • 对于 dp[0][...],即一个物品也不考虑的情况,背包的价值总是 0。
    • 对于 dp[...][0],即背包容量为 0 的情况,背包的价值也总是 0。
  3. 递推关系(状态转移方程):

    • 对于每一个物品 i 和每一个可能的重量 w,我们需要做出一个决策:是否将物品 i 放入背包。
    • 如果不放物品 i,则 dp[i][w] = dp[i-1][w] —— 也就是说,当前的最大价值与前 i-1 个物品时的最大价值相同。
    • 如果放物品 i,我们必须确保当前背包的剩余容量至少是物品 i 的重量 (weights[i-1] <= w),在这种情况下,dp[i][w] = dp[i-1][w-weights[i-1]] + values[i-1] —— 也就是说,当前的最大价值是物品 i 的价值加上剩余重量在前 i-1 个物品中能得到的最大价值。
  4. 填表

    • 我们按照递推关系来填表 —— 从较小的 i 和 w 开始,直到 i 等于物品个数,w 等于背包最大重量。
  5. 解的构造

    • 表格填完后,dp[n][maxWeight] 就是答案 —— 即考虑所有物品和最大背包重量时的最大价值。

        补充-递推公式的推导:

        假设我们有n个物品,每个物品的重量为weights[i],价值为values[i],背包的最大重量限制为maxWeight。我们定义dp[i][w]为考虑前i个物品(物品编号为0i-1),在背包重量限制为w的情况下,能够得到的最大总价值。我们想求的最终答案是dp[n][maxWeight]

        对于每个物品i(从1开始计数,对应数组下标为i-1),以及每个可能的重量限制w,我们面临两种选择:

  1. 不包含当前物品:如果我们决定不包含当前考虑的物品i-1,那么最大价值不会因为当前物品的存在而改变,所以它等于没有考虑当前物品时的最大价值,即dp[i-1][w]

  2. 包含当前物品:如果我们决定包含当前考虑的物品i-1,前提是这个物品的重量不超过当前的重量限制w(即weights[i-1] <= w)。此时,我们需要加上这个物品的价值values[i-1],同时,背包的剩余重量变为w - weights[i-1],因此我们还需要加上在新的重量限制下,考虑前i-1个物品时的最大价值,即dp[i-1][w-weights[i-1]] + values[i-1]

        因此,递推公式如下:

  • 如果weights[i-1] > w(当前物品重量超过背包限制),则dp[i][w] = dp[i-1][w]
  • 否则,dp[i][w] = max(dp[i-1][w], dp[i-1][w-weights[i-1]] + values[i-1])

        这个递推公式基于以下逻辑:对于每个物品,我们都做出是否包含它的决定,以确保在不超过背包重量限制的情况下达到最大价值。这种方式确保了我们能够考虑所有可能的组合,并找到最优解。

示例

        初始状态

        首先,初始化一个表`dp`,其中`dp[i][j]`代表在只考虑前`i`个物品,且背包容量为`j`时的最大价值。初始化时,所有值均为0。

        物品情况:
        - 物品0:价值15,重量1
        - 物品1:价值20,重量3
        - 物品2:价值30,重量4

        动态规划表格是这样的(行表示物品,列表示重量):

重量        0   1   2   3   4
不选物品    0   0   0   0   0

        加入物品0

        加入物品0(价值15,重量1)后,我们更新表格。对于重量1及以上的列,我们可以加入物品0。

重量        0   1   2   3   4
不选物品    0   0   0   0   0
加入物品0   0  15  15  15  15

        加入物品1

        接着,我们考虑加入物品1(价值20,重量3)。我们更新表格,考虑对于每个重量限制,在不超过该重量的情况下,是否加入物品1能获得更高的价值。

重量        0   1   2   3   4
不选物品    0   0   0   0   0
加入物品0   0  15  15  15  15
加入物品1   0  15  15  20  20

        在重量为4时,我们比较加入物品1后的价值与之前的状态。但是,我们忽略了一种可能:加入物品1(重量3,价值20)后,还可以再加入物品0(重量1,价值15),因此,对于重量4,最大价值应该是35(物品0和物品1的组合)。

        加入物品2

        最后,我们考虑加入物品2(价值30,重量4)。同样,我们更新表格,考虑对每个重量限制,加入物品2是否能带来更高的价值。

重量        0   1   2   3   4
不选物品    0   0   0   0   0
加入物品0   0  15  15  15  15
加入物品1   0  15  15  20  35
加入物品2   0  15  15  20  35

        在重量为4的情况下,加入物品2的价值(30)并不比已有的组合(物品0和物品1,总价值35)更优,因此我们保持原有的最大价值不变。

        最终结果

        最终,我们得到的动态规划表如下,表明在背包重量限制为4时,我们能获得的最大价值是35,通过组合物品0(价值15,重量1)和物品1(价值20,重量3)。

重量        0   1   2   3   4
不选物品    0   0   0   0   0
加入物品0   0  15  15  15  15
加入物品1   0  15  15  20  35
加入物品2   0  15  15  20  35

        因此,最终答案是,在确保总重量不超过4的条件下,我们最后得到的背包中的最大价值是35。

梳理

        这个方法能够实现的原因在于它利用了动态规划(Dynamic Programming, DP)的两个关键性质:最优子结构和重叠子问题。

        最优子结构意味着问题的最优解包含着其子问题的最优解。对于0-1背包问题来说,每增加一个物品的选择,都是基于之前所有物品选择的最优解上进行的新增决定。换句话说,在考虑是否加入当前物品时,我们可以依赖于之前物品的决策结果,这些决策结果是以最大化价值为目标的。

        重叠子问题指的是在解决问题的过程中,相同的问题会被多次解决。在0-1背包问题中,当我们分别计算每一个重量限制下的最大价值时,会重复计算某些重量限制下的最大价值。通过动态规划,我们可以将这些价值存储在一个表中,避免重复计算,这就是为什么我们使用一个二维数组来存储每个子问题的答案。

        在填充动态规划表时,我们从最小的子问题开始,即背包没有任何物品时的价值是0。然后逐步增加物品和重量,直到考虑了所有物品和所有重量限制。在每一步,针对每一个重量限制,我们都计算了两种情况:

        1. 不加入当前的物品,直接使用之前同样重量限制下的最大价值。
        2. 尝试加入当前的物品,将物品的价值加上剩余重量限制下的最大价值。

        通过比较上述两种情况的价值,我们可以选择较大的一个作为当前重量限制和当前物品下的最大价值。这个过程一直持续到表格被填满,最终我们在表格的右下角得到的值就是我们能够拿到的最大价值。

        简单来说,这方法之所以行之有效,是因为它将一个复杂问题分解为一系列叠加的简单问题并解决它们,同时保留了要求的全局最优解。通过表格的逐步填充,我们保证了在任何给定重量限制下,我们都是在做出最佳决策,以此计算出全局最优解。

代码

#include <iostream> // 引入标准输入输出库
#include <vector> // 引入向量(动态数组)库
using namespace std; // 使用标准命名空间,简化代码

// 动态规划解决 0-1 背包问题的函数
int knapsack(const vector<int>& weights, const vector<int>& values, int maxWeight) {
    int n = weights.size(); // 物品数量
    // 初始化动态规划表,所有值起始为0
    vector<vector<int>> dp(n + 1, vector<int>(maxWeight + 1, 0)); 

    // 使用动态规划构建 dp 数组
    for (int i = 1; i <= n; ++i) { // 遍历每个物品
        for (int w = 1; w <= maxWeight; ++w) { // 遍历每种重量限制
            // 如果当前物品可以加入背包
            if (weights[i - 1] <= w) {
                // 选择加入当前物品和不加入当前物品中价值更大的一个
                dp[i][w] = max(dp[i - 1][w], values[i - 1] + dp[i - 1][w - weights[i - 1]]);
            } else {
                // 如果不能加入当前物品,保持之前的最大价值
                dp[i][w] = dp[i - 1][w];
            }
        }
    }

    // 返回最大值,即考虑所有物品且不超过最大重量限制时的最大价值
    return dp[n][maxWeight];
}

int main() {
    int maxWeight = 4; // 背包的最大重量限制
    vector<int> weights = {1, 3, 4}; // 物品的重量
    vector<int> values = {15, 20, 30}; // 物品的价值
    
    // 输出背包能达到的最大总价值
    cout << "背包能达到的最大总价值为 "
         << knapsack(weights, values, maxWeight) << endl;

    return 0; // 程序正常结束
}

        时间复杂度:O(n * maxWeight)

        空间复杂度:O(n * maxWeight)

打卡

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/393961.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

PCL库学习及ROS使用

PCL库学习 c_cpp_properties.json {"configurations": [{"name": "Linux","includePath": ["${workspaceFolder}/**","/usr/include","/usr/local/include"],"defines": [],"compiler…

Linux第60步_“buildroot”构建根文件系统第2步_配置“buildroot下的busybox”并测试“buildroot”生成的根文件系统

1、查看“buildroot下的busybox”安装路径 打开终端 输入“ls回车” 输入“cd linux回车/”&#xff0c;切换到到“linux”目录 输入“ls回车”&#xff0c;查看“linux”目录下的文件和文件夹 输入“cd buildroot/回车”&#xff0c;切换到到“buildroot”目录 输入“ls…

ClickHouse迎战十亿行数据的挑战

本文字数&#xff1a;6782&#xff1b;估计阅读时间&#xff1a;17 分钟 作者&#xff1a;Dale McDiarmid 审校&#xff1a;庄晓东&#xff08;魏庄&#xff09; 本文在公众号【ClickHouseInc】首发 本月初&#xff0c;Decodable 公司的 Gunnar Morling 提出了一项为期一月挑战…

接口测试怎么进行,如何做好接口测试

一、什么是接口&#xff1f; 接口测试主要用于外部系统与系统之间以及内部各个子系统之间的交互点&#xff0c;定义特定的交互点&#xff0c;然后通过这些交互点来&#xff0c;通过一些特殊的规则也就是协议&#xff0c;来进行数据之间的交互。 二、 常用接口采用方式&#x…

API自动化测试你以为很难?看完这篇文章直接打开你的任督二脉

API测试已成为日常的测试任务之一&#xff0c;为了提高测试效率&#xff0c;减少重复的手工操作&#xff0c;API自动化测试也逐渐变得愈加重要&#xff0c;本文是自己在API自动化测试方面的一些经验积累和心得、汇总成文&#xff0c;以飨读者 我相信自动化技能已经成为高级测试…

单调栈题目总结

单调栈 496. 下一个更大元素 I 503. 下一个更大元素 II 739. 每日温度 6227. 下一个更大元素 IV 模版归纳 「单调栈」顾名思义就是具有单调性的栈结构&#xff0c;一般常用于找到下一个更大的元素&#xff0c;即当前元素右侧第一个更大的元素 看下面一个例子&#xff1a…

消毒柜行业分析:市场渗透率不足20%

目前消毒柜仍然属于“小众”品类&#xff0c;疫情前期市场渗透率也不足20%。有业内人士表示&#xff0c;多年来消毒柜零售量规模基本在400万台左右徘徊&#xff0c;这个角度看&#xff0c;消毒柜是具有自身的产品消费人群的&#xff0c;其市场相对稳定&#xff0c;而且消毒柜的…

DoRA(权重分解低秩适应):一种新颖的模型微调方法

来自&#xff1a;小互 DoRA&#xff08;权重分解低秩适应&#xff09;&#xff1a;一种新颖的模型微调方法 DoRA在LoRA的基础上进一步发展&#xff0c;通过将预训练权重分解为“幅度”和“方向”两个部分进行微调。 这种权重分解方法允许DoRA更精细地控制模型的学习过程&…

error: ‘QWidget‘ file not found

说明你没有加载 widgets模块 缺少widgets&#xff0c;就报错

mysql 2-17

UNION关键字和UNION ALL 自然连接 USING使用 函数 单行函数 基本函数 三角函数 指数和对数 进制间的转换 字符串函数 时间和日期函数 计算日期和时间的函数 日期的格式化和解析 流程控制函数

这样用TVS管

对于工程师来说&#xff0c;浪涌保护不仅仅是选择合适的电源板或者拔下几根电缆&#xff0c;主要涉及在 PCB 布局中放置瞬态保护组件并应用明确的接地策略。 TVS 二极管是用于保护PCB布局中组件的常用组件&#xff0c;这些组件放置在数据线上&#xff0c;一旦电路中接收到ESD脉…

激活函数30年回顾总结,全paper第一份详尽研究来了!

B站&#xff1a;啥都会一点的研究生公众号&#xff1a;啥都会一点的研究生 新年好&#xff0c;离退休又近了一年 假期躺平未更新&#xff0c;但该保存的素材及热点还是拿小本本记了下来&#xff0c;如这篇今年2月14号arXiv上发表的长达100页神经网络中激活函数大总结文章就进…

综合练习

目录 查询每个员工的编号、姓名、职位、基本工资、部门名称、部门位置 确定要使用的数据表 确定已知的关联字段 查询每个员工的编号、姓名、职位、基本工资、工资等级 确定要使用的数据表 确定已知的关联字段 查询每个员工的编号、姓名、职位、基本工资、部门名称、工资…

string的用法

概念 可代替字符数组来存储字符串 访问 string name[i];//下标访问 string::iterator it;//迭代器访问常用函数 1.begin():获得字符串首地址 2.end():获得字符串末地址 3.&#xff1a;字符串的加法&#xff0c;可将两个字符串拼接起来 4.比较符&#xff1a;&#xff0c;>…

GET与 POST

资料来源 : 小林coding 小林官方网站 : 小林coding (xiaolincoding.com) GET 和 POST 有什么区别? 根据 REC 规范&#xff0c;GET的语义是从服务器获取指定的资源&#xff0c;这个资源可以是静态的文本、页面、图片视频等。GET请求的参数位置一般是写在 URL 中&#xff0c;UR…

Python Selenium实现自动化测试及Chrome驱动使用!

本文将介绍如何使用Python Selenium库实现自动化测试&#xff0c;并详细记录了Chrome驱动的使用方法。 通过本文的指导&#xff0c;读者将能够快速上手使用Python Selenium进行自动化测试。 并了解如何配置和使用Chrome驱动来实现更高效的自动化测试。 一、Python Selenium简…

ClickHouse监控及备份

第1章 ClickHouse监控概述 第2章 Prometheus&Grafana的安装 第3章 ClickHouse配置 第4章 Grafana集成Prometheus 第5章 备份及恢复

2024 前端面试题(GPT回答 + 示例代码 + 解释)No.114 - No.121

本文题目来源于全网收集&#xff0c;答案来源于 ChatGPT 和 博主&#xff08;的小部分……&#xff09; 格式&#xff1a;题目 h3 回答 text 参考大佬博客补充 text 示例代码 code 解释 quote 补充 quote 上一篇链接&#xff1a;2024 前端面试题&#xff08;GPT回答 示例…

Linux系统:iptables 防火墙

目录 一、安全技术与防火墙 1、安全技术概念 2、防火墙 2.1 防火墙概念 2.2 防火墙分类 2.3 linux的防火墙Netfilter 2.4 防火墙工具介绍 2.5 netfilter 和 iptables 的关系 二、iptables 1、概念 2、五表五链 2.1 五个table表 2.2 五个chain链 2.3 内核中数据包…

全网最详细的从0到1的turbo pnpm monorepo的前端工程化项目[搭建篇]

全网最详细的从0到1的turbo pnpm monorepo的前端工程化项目[搭建篇] 引言相关环境技术栈初始化工程安装turbo配置pnpm-workspace安装husky安装lint-staged安装eslint安装prettier配置 .editorconfig配置 .gitignore初步项目结构结语 引言 最近各种原因&#xff0c;生活上的&am…