盖子的c++小课堂——第二十三讲:背包问题

前言

又是一次漫长的更新(我真不是故意的aaaaaaaaaaaaaaa),先不多说了,直接给我~坐下~说错了说错了,直接开始~

背包问题----动态规划

背包问题(knapsack problem)

动态规划(dynamic programming)

01背包:可行性

对一个背包最多载重m斤,共有n件物品,第i件物品重量为w[i]。对每件物品可选择拿走或不拿。请问能否恰好拿到总重量为m斤?

 

 01决策:不选0,选1

凑数:可行性

目标凑出数字m,有n个数字可以使用,第i个数字为x[i]。对每一个数字最多可以选用1次。请问能否恰好凑出数字m?

 01决策:不选0,选1

简化问题

01背包:可行性

f[i][j]表示只用前i个数字能否凑出j

初始条件 

f[0][0]=1

状态转移方程

若j<x[i]——f[i][j]=f[i-1][j]

若j>=x[i]——f[i][j]=f[i-1][j]或f[i-1][j-x[i]]

01背包:3种问题

可行性判定问题

用n个物品能否恰好凑出m斤重量

方案计数问题

用n个物品能否恰好凑出m斤各种方案

最优化问题

用n个物品凑出不超过m斤时最多几斤

01背包

关于01背包,建议结合我的B站视频一起学习,相信会对你彻底理解背包问题有很大帮助!

带你学透0-1背包问题!| 关于背包问题,你不清楚的地方,这里都讲了!| 动态规划经典问题 | 数据结构与算法_哔哩哔哩_bilibili​www.bilibili.com/video/BV1cg411g7Y6​编辑icon-default.png?t=N7T8https://link.zhihu.com/?target=https%3A//www.bilibili.com/video/BV1cg411g7Y6带你学透01背包问题(滚动数组篇) | 从此对背包问题不再迷茫!_哔哩哔哩_bilibili​www.bilibili.com/video/BV1BU4y177kY​编辑icon-default.png?t=N7T8https://link.zhihu.com/?target=https%3A//www.bilibili.com/video/BV1BU4y177kY

有N件物品和一个最多能被重量为W 的背包。第i件物品的重量是weight[i],得到的价值是value[i] 。每件物品只能用一次,求解将哪些物品装入背包里物品价值总和最大。

 

这是标准的背包问题,以至于很多混丝看了这个自然就会想到背包,甚至都不知道暴力的解法应该怎么解了。

这样其实是没有从底向上去思考,而是习惯性想到了背包,那么暴力的解法应该是怎么样的呢?

每一件物品其实只有两个状态,取或者不取,所以可以使用回溯法搜索出所有的情况,那么时间复杂度就是O(2^n),这里的n表示物品数量。

 二维dp数组01背包

确定dp数组以及下标的含义

对于背包问题,有一种写法, 是使用二维数组,即dp[i][j] 表示从下标为[0-i]的物品里任意取,放进容量为j的背包,价值总和最大是多少?

要时刻记着这个dp数组的含义,下面的一些步骤都围绕这dp数组的含义进行的,如果哪里看懵了,就来回顾一下i代表什么,j又代表什么。

确定递推公式

再回顾一下dp[i][j]的含义:从下标为[0-i]的物品里任意取,放进容量为j的背包,价值总和最大是多少。

那么可以有两个方向推出来dp[i][j],

  • 由dp[i - 1][j]推出,即背包容量为j,里面不放物品i的最大价值,此时dp[i][j]就是dp[i - 1][j]
  • 由dp[i - 1][j - weight[i]]推出,dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]的时候不放物品i的最大价值,那么dp[i - 1][j - weight[i]] + value[i] (物品i的价值),就是背包放物品i得到的最大价值

所以递归公式: dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

dp数组如何初始化

关于初始化,一定要和dp数组的定义吻合,否则到递推公式的时候就会越来越乱。

首先从dp[i][j]的定义出发,如果背包容量j为0的话,即dp[i][0],无论是选取哪些物品,背包价值总和一定为0。

状态转移方程 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); 可以看出i 是由 i-1 推导出来,那么i为0的时候就一定要初始化。

dp[0][j],即:i为0,存放编号0的物品的时候,各个容量的背包所能存放的最大价值。

代码如下:

for (int j = weight[0]; j <= bagWeight; j++) {
    dp[0][j] = value[0];
}

dp[0][j] 和 dp[i][0] 都已经初始化了,那么其他下标应该初始化多少呢?

dp[i][j]在推导的时候一定是取价值最大的数,如果题目给的价值都是正整数那么非0下标都初始化为0就可以了,因为0就是最小的了,不会影响取最大价值的结果。

如果题目给的价值有负数,那么非0下标就要初始化为负无穷了。例如:一个物品的价值是-2,但对应的位置依然初始化为0,那么取最大值的时候,就会取0而不是-2了,所以要初始化为负无穷。

而背包问题的物品价值都是正整数,所以初始化为0,就可以了。

这样才能让dp数组在递归公式的过程中取最大的价值,而不是被初始值覆盖了。

最后初始化代码如下:

vector<vector<int>> dp(weight.size() + 1, vector<int>(bagWeight + 1, 0));
for (int j = weight[0]; j <= bagWeight; j++) {
    dp[0][j] = value[0];
}

 那么问题来了,先遍历物品还是先遍历背包重量呢?

其实都可以!! 但是先遍历物品更好理解

那么我先给出先遍历物品,然后遍历背包重量的代码。

// weight数组的大小 就是物品个数
for(int i = 1; i < weight.size(); i++) { // 遍历物品
    for(int j = 0; j <= bagWeight; j++) { // 遍历背包容量
        if (j < weight[i]) dp[i][j] = dp[i - 1][j]; // 这个是为了展现dp数组里元素的变化
        else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

    }
}

 先遍历背包,再遍历物品,也是可以的

例如这样:

// weight数组的大小 就是物品个数
for(int j = 0; j <= bagWeight; j++) { // 遍历背包容量
    for(int i = 1; i < weight.size(); i++) { // 遍历物品
        if (j < weight[i]) dp[i][j] = dp[i - 1][j];
        else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
    }
}

为什么也是可以的呢?

要理解递归的本质和递推的方向

dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); 递归公式中可以看出dp[i][j]是靠dp[i-1][j]和dp[i - 1][j - weight[i]]推导出来的。

dp[i-1][j]和dp[i - 1][j - weight[i]] 都在dp[i][j]的左上角方向(包括正左和正上两个方向)

其实背包问题里,两个for循环的先后循序是非常有讲究的,理解遍历顺序其实比理解推导公式难多了

总结

讲了这么多才刚刚把二维dp的01背包讲完,这里大家其实可以发现最简单的是推导公式了,推导公式估计看一遍就记下来了,但难就难在如何初始化和遍历顺序上

可能有的混丝并没有注意到初始化和遍历顺序的重要性,我们后面做力扣上背包面试题目的时候,大家就会感受出来了。

(这真是n年一度的大更新)

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

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

相关文章

【Redis】非关系型数据库之Redis的主从复制、哨兵和集群高可用

目录 一、主从复制、哨兵、集群的区别 二、主从复制 2.1主从复制的作用 2.2主从复制的原理 2.3主从复制的实操 步骤一&#xff1a;环境准备 步骤二&#xff1a;安装Redis以及配置文件修改 Redis的主从配置文件都一样 步骤四&#xff1a;验证主从复制 三、哨兵 3.1哨兵…

numpy100练习题,包含相应使用函数解释

取自github开源项目&#xff1a;numpy100题 文章目录 1. 导入numpy库并简写为 np (★☆☆)2. 打印numpy的版本和配置说明 (★☆☆)3. 创建一个长度为10的空向量 (★☆☆)4. 如何找到任何一个数组的内存大小&#xff1f; (★☆☆)5. 如何从命令行得到numpy中add函数的说明文档?…

2024年1月9日学习总结

目录 学习目标学习内容联邦学习基础&#xff1a;why, what, howwhy&#xff1f;what&#xff1f;how&#xff1f; 联邦学习的例子——CIFAR-10数据集&#xff08;分类问题&#xff09;1、import libararies2、hyper-parameters3、加载并且划分数据4、创建神经网络模型5、helper…

Spark Core--加强

RDD的持久化 RDD缓存 当RDD被重复使用&#xff0c;或者计算该RDD比较容易出错&#xff0c;而且需要消耗比较多的资源和时间的时候&#xff0c;我们就可以将该RDD缓存起来。 主要作用: 提升Spark程序的计算效率 注意事项: RDD的缓存可以存储在内存或者是磁盘上&#xff0c;甚至…

RBAC权限管理概念

基于RBAC模型的权限设计&#xff1a;如何设计系统权限体系&#xff1f; | 人人都是产品经理 一&#xff0c;什么是RBAC RBAC(基于角色的权限控制)模型的核心是在用户和权限之间引入了角色的概念。取消了用户和权限的直接关联&#xff0c;改为通过用户关联角色、角色关联权限的…

虾皮如何查看自己的店铺

在虾皮&#xff08;Shopee&#xff09;平台上查看自己的店铺是非常重要的&#xff0c;因为它可以帮助您了解店铺的运营情况、管理商品和处理客户服务等。下面是在虾皮平台上查看店铺的步骤&#xff1a; 先给大家推荐一款shopee知虾数据运营工具知虾免费体验地址&#xff08;复制…

nn网络层-卷积层

一、1d/2d/3d Convolution 卷积运算&#xff1a;卷积核在输入信号&#xff08;图像&#xff09;上滑动&#xff0c;相应位置上进行乘加卷积核&#xff1a;又称为滤波器&#xff0c;过滤器&#xff0c;可认为是某种模式&#xff0c;某种特征。卷积过程类似于用一个模版去图像上…

【JAVA】怎么确保一个集合不能被修改

&#x1f34e;个人博客&#xff1a;个人主页 &#x1f3c6;个人专栏&#xff1a; JAVA ⛳️ 功不唐捐&#xff0c;玉汝于成 目录 前言 正文 示例&#xff1a; 不可修改的List&#xff1a; 不可修改的Set&#xff1a; 不可修改的Map&#xff1a; 结语 我的其他博…

强化学习在生成式预训练语言模型中的研究现状简单调研

1. 绪论 本文旨在深入探讨强化学习在生成式预训练语言模型中的应用&#xff0c;特别是在对齐优化、提示词优化和经验记忆增强提示词等方面的具体实践。通过对现有研究的综述&#xff0c;我们将揭示强化学习在提高生成式语言模型性能和人类对话交互的关键作用。虽然这些应用展示…

STM32F103C8T6内部自带Bootloader模式之使用FlyMcu烧写程序

简介 实现自己的Bootloader前, 使用一下STM32内部自带的Bootloader对STM进行烧写 步骤 下载FlyMCU 参考 普中STM32-PZ6806L 使用FlyMcu串口烧录程序 Boot选择 Boot0->1 , Boot1->0 进到系统存储器 打开FlyMCU 1 选择串口波特率 2 选择程序 3 不需要使用辅助引脚 4 开…

Linux网络配置与抓包工具介绍

目录 一、配置命令 1. ifconfig 1.1 概述信息解析 1.2 常用格式 2. ip 2.1 ip link 数据链路层 2.2 ip addr 网络层 2.3 路由 3. hostname 3.1 临时修改主机名 3.2 永久修改主机名 4. route 5. netstat 6. ss 7. ping 8. traceroute 9. nslookup 10. 永久修…

书生·浦语大模型全链路开源体系 学习笔记 第三课

huggingface-cli: command not found 按照该文档解决即可 https://github.com/huggingface/huggingface_hub/issues/1079 具体如下&#xff1a; 1、确保环境已将安装huggingface-cli 2、版本需要旧版&#xff0c;pip install huggingface_hub0.20.1 3、再按如下执行 # T…

WCF几种寄宿方式IIS、Winform、控制台、Windows服务

WCF寄宿方式是一种非常灵活的操作,可以在IIS服务、Windows服务、Winform程序、控制台程序中进行寄宿,从而实现WCF服务的运行,为调用者方便、高效提供服务调用。本文分别对这几种方式进行详细介绍并开发例子进行说明,以求大家对WCF寄宿的方式进行全面的认识和了解。 1、 WC…

计算机毕业设计 基于SpringBoot的项目申报系统的设计与实现 Java实战项目 附源码+文档+视频讲解

博主介绍&#xff1a;✌从事软件开发10年之余&#xff0c;专注于Java技术领域、Python人工智能及数据挖掘、小程序项目开发和Android项目开发等。CSDN、掘金、华为云、InfoQ、阿里云等平台优质作者✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精…

探索雷盛537威士忌的魅力:从观色、闻香到品鉴

威士忌&#xff0c;这一源于苏格兰的特别烈酒&#xff0c;以其丰富的味蕾和特别的魅力征服了全球的品鉴者。品鉴威士忌不仅仅是一种感官体验&#xff0c;更是一种探索和发现的旅程。在本文中&#xff0c;我们将以雷盛537威士忌为例&#xff0c;与您深入了解品鉴威士忌的全过程&…

React-Hoc高阶组件与css-in-js技术

Hoc高阶组件 Higher - Order Components&#xff1a;在原有组件基础之上加工后新生成得到的新组件。【高阶组件】 const NewComponent HOC(YourComponent) 通俗的来讲&#xff0c;高阶组件就相当于手机壳&#xff0c;通过包装组件&#xff0c;增强组件功能。 HOC实现步骤&…

三分钟轻松搞懂 HashMap 死循环问题!

三分钟轻松搞懂 HashMap 死循环问题&#xff01; HashMap 死循环发生在 JDK 1.7 版本中&#xff0c;形成死循环的原因是 HashMap 在 JDK 1.7 使用的是头插法&#xff0c;头插法 链表 多线程并发 HashMap 扩容&#xff0c;这几个点加在一起就形成了 HashMap 的死循环。 前置…

Adding Conditional Control to Text-to-Image Diffusion Models——【代码复现】

官方实现代码地址&#xff1a;lllyasviel/ControlNet: Let us control diffusion models! (github.com) 一、前言 此项目的使用需要显存大于8G&#xff0c;训练自己的ControlNet或需要更大&#xff0c;因此请注意查看自身硬件是否符合。 在此之前请确保已经安装好python以及…

【UE Niagara学习笔记】05 - 喷射火焰顶部的蓝色火焰

在上一篇博客&#xff08;【UE Niagara学习笔记】04 - 火焰喷射时的黑烟效果&#xff09;的基础上继续实现在火焰喷射的起点位置生成蓝色火焰的效果。 目录 效果 步骤 1. 创建新的发射器 2. 减少粒子生成数量 3. 减小粒子初始大小 4. 减少粒子喷射距离 5. 减少粒子初始…

在Linux上搭建Maven仓库

目录 一、下载安装包二、安装maven三、修改配置文件settings.xml四、配置环境变量五、测试maven是否可用 一、下载安装包 我在这里为大家准备好了apache-maven-3.5.0-bin.tar.gz&#xff0c;百度网盘下载链接如下&#xff1a; 链接&#xff1a;https://pan.baidu.com/s/1bGun…