动态规划解0-1背包问题(超详细理解)
前言:
好久没写0-1背包问题了,都有些不记得了,写这篇文章给自己以后做简单参考,如果能同时帮到读者,不胜荣幸。
正文
0-1背包问题是这样的一个问题,假设有一个背包,其容量为 capacity 。在地上有一堆物品,其数量为 n ,每个物品有两种属性:重量 w和价值 v。
要求就是,找到一个物品的组合,使得它们的重量小于等于最大容量,并且其价值最大。
动态规划的思路解0-1背包问题:
首先建立一个二维数组dp,其中dp[i][j]表示仅使用前i个物品的情况下,当背包容量为j时,所能获得的最大价值。也即:从前i个物品里面选取一些物品,这些物品的总重量小于等于j,但是它们的价值之和最大,这个最大价值和就记为dp[i][j]。
dp的行宽为n,表示总共有n个物品,列宽为capacity,表示背包的最大容量为capacity。
大致是这样:

假设有n个物品,并用1-n分别给各个物品编号,wi,vi分别表示第i个物品的重量和价值。
那么第一行的第j列表示,当仅使用物品1、背包容量为j时,所能装进背包里面的最大价值。
所以,在第一行当中:
(1)若w1 > j,那么背包容量j是无法容纳第一个物品的重量的,此时应填0
(2)若w1 <= j,那么背包容量是可以容下第一个物品的重量的,此时应填v1.
所以第一行的元素只能填0或者v1,而且前半段是0,后半段是v1
假设n==10,背包容量为3(最终容量)
1,2,3(各个物品的编号)
2,7,1(各个物品的重量)
1,2,3(各个物品的价值)
假设w1==7,那么第一行如下:

设i>1,那么对于第i行的第j列,应该这么填:
(1)wi > j时,那么即使把背包里面已经装进去的东西全部腾空,也不足以装下第i个物品。
此时dp[i][j] = dp[i-1][j]。也就是说,考虑前i个物品和前i-1个物品是一样的结果。
(2)wi <= j时,可以考虑把第i个物品放进去
(2-1)假如要把第i个物品放进去,那么第i个物品会占据wi的容量,剩下的容量最大能装多少价值的物品呢?毫无疑问,应该最大能装dp[i-1][j-wi]的价值,这是因为dp[m][n]就表示仅使用前m个物品,在容量为n时所能装入的最大价值。也即dp[i][j] = dp[i-1][j-wi] + vi。
(2-2)假如不把第i个物品放进去,那么价值总量维持不变,也即:dp[i][j] = dp[i-1][j]。
(2-3)
那到底要不要把第i个物品放进去呢?有人可能会说,既然能放进去,那为什么不放进去呢?
放进去的话,价值不是更大吗?事实上不一定,因为这里所说的能放进去是指,把背包里面
已经放进去的东西腾空后,第i个物品能放进去。但是强行把第i个物品放进去之后,有可能
导致原来已经放进去的某些物品被挤得没有空间放了,这就有可能导致总价值量的减小。
所以,当wi <= j时,dp[i][j] = max{dp[i-1][j-wi] + vi , dp[i-1][j]}
所以最终填表就是:

所以,从表格中可以看出来,当背包容量为3,物品个数为3,
各个物品编号为:1,2,3
各个物品重量为:2,7,1
各个物品价值为:1,2,3时,
能装进背包里面的最大价值为4(表格右下角的数)
练习:
这张图片是力扣上面的题目,也是0-1背包问题

写在最后:如有错误,敬请指正,礼貌交流,感激不尽。
相关文章:
动态规划解0-1背包问题(超详细理解)
前言: 好久没写0-1背包问题了,都有些不记得了,写这篇文章给自己以后做简单参考,如果能同时帮到读者,不胜荣幸。 正文 0-1背包问题是这样的一个问题,假设有一个背包,其容量为 capacity 。在地…...
有哪些可能引起前端安全的问题?
跨站脚本 (Cross-Site Scripting, XSS) ⼀种代码注⼊⽅式,为了与 CSS 区分所以被称作 XSS。早期常⻅于⽹络论坛, 起因是⽹站没有对⽤户的输⼊进⾏严格的限制, 使得攻击者可以将脚本上传到帖⼦让其他⼈浏览到有恶意脚本的⻚⾯, 其注⼊⽅式很简单包括但不限于 JavaScript / CSS …...
【Unity实战100例】用户头像圆形遮罩使用Shader不用Mask组件
目录 一.创建材质 二.创建Shader文件编写Shader代码 三.Image材质设置 源码:https://download.csdn.net/download/qq_37310110/88196529 前言:我们在使用Unity的自带组件Mask的时候会出现毛边现象很难处理掉,这里我们使用着色器shader来进行处理就不会出现毛边现象。...
arm-linux-gnueabihf-g++ gcc编译、优化命令 汇总
gcc优化选项,可在编译时间,目标文件长度,执行效率三个维度,进行不同的取舍和平衡。 gcc 常用编译选项 arm-linux-gnueabihf-g -O3 -marcharmv7-a -mcpucortex-a9 -ftree-vectorize -mfpuneon -mfpuvfpv3-fp16 -mfloat-abihard -…...
vmwera中安装的centos8出现ifconfig不可用
刚刚在虚拟机中装好centos结果发现自己的ifconfig命令不可用。 看一下环境变量里有没有ifconfig命令的路径,因为ifconfig是在/sbin路径下的,root用户登录进去才可以运行,先看一下root用户的环境变量。 root用户的环境变量里是有/sbin路径的&a…...
线性表中的时间复杂度
线性表 一、顺序表示的线性表 插入操作的时间复杂度 最好情况: O ( 1 ) O(1) O(1)。(新元素插到表尾,不需要移动元素)最坏情况: O ( n ) O(n) O(n)。(新元素插到表头,需要将原有的n个元素全部…...
ensp与虚拟机搭建测试环境
1.虚拟机配置 ①首先确定VMnet8 IP地址,若要修改IP地址,保证在启动Ensp前操作 ②尽量保证NAT模式 2.ensp配置 (1)拓扑结构 (2)Cloud配置 ①首先点击 绑定信息 UDP → 增加 ②然后点击 绑定信息 VMware ... → 增加 ③最后在 端口映射设置上点击双向通…...
linux内核中的 指针 和 unsigned long
文章目录 1.指针的来源2.指针的定义:3.字长和数据类型4.Linux内核为什么常用unsigned long来替代指针?参考资料 1.指针的来源 方便引用一个内存地址。 给定一个内存地址,CPU就可以取出该地址的数据。 给定一个内存地址,CPU就可以…...
STM32--GPIO
文章目录 GPIO简介GPIO的基本结构GPIO位结构GPIO模式LED和蜂鸣器LED闪烁工程及程序原码代码: 蜂鸣器工程和程序原码代码 传感器光敏传感器控制蜂鸣器工程代码 GPIO简介 GPIO(General Purpose Input Output)是通用输入/输出口的简称。它是一种…...
剑指 Offer ! 61. 扑克牌中的顺子
参考资料:力扣K神的讲解 剑指 Offer 61. 扑克牌中的顺子 简单 351 相关企业 从若干副扑克牌中随机抽 5 张牌,判断是不是一个顺子,即这5张牌是不是连续的。2~10为数字本身,A为1,J为11,Q为12&…...
《玩转Python数据分析专栏》大纲
欢迎来到《玩转Python数据分析分类专栏》!在这个专栏中,我们将带您深入探索数据分析的世界,以Python为工具,解析各个领域的实际应用场景。通过100篇教程,我们将逐步引领您从入门级到高级,从基础知识到实战技巧,助您成为一名优秀的数据分析师。 专栏目标 本专栏旨在帮助…...
Zabbix自动注册服务器及部署代理服务器
文章目录 一.zabbix自动注册1.什么是自动注册2.环境准备3.zabbix客户端配置4.在 Web 页面配置自动注册5.验证自动注册 二.部署 zabbix 代理服务器1.分布式监控的作用:2.环境部署3.代理服务器配置4.客户端配置5.web页面配置5.1 删除原来配置5.2 添加代理5.3 创建主机…...
SpringBoot下使用自定义监听事件
事件机制是Spring的一个功能,目前我们使用了SpringBoot框架,所以记录下事件机制在SpringBoot框架下的使用,同时实现异步处理。事件机制其实就是使用了观察者模式(发布-订阅模式)。 Spring的事件机制经过如下流程: 1、自定义事件…...
并发编程面试题1
并发编程面试题1 一、原子性高频问题: 1.1 Java中如何实现线程安全? 多线程操作共享数据出现的问题。 锁: 悲观锁:synchronized,lock乐观锁:CAS 可以根据业务情况,选择ThreadLocal,让每个…...
【对于一维信号的匹配】对一个一维(时间)信号y使用自定义基B执行匹配追踪(MP)研究(Matlab代码实现)
💥💥💞💞欢迎来到本博客❤️❤️💥💥 🏆博主优势:🌞🌞🌞博客内容尽量做到思维缜密,逻辑清晰,为了方便读者。 ⛳️座右铭&a…...
【Oracle 数据库 SQL 语句 】积累1
Oracle 数据库 SQL 语句 1、分组之后再合计2、显示不为空的值 1、分组之后再合计 关键字: grouping sets ((分组字段1,分组字段2),()) select sylbdm ,count(sylbmc) a…...
Django中级指南:理解并实现Django的模型和数据库迁移
Django 是一个极其强大的 Python Web 框架,它提供了许多工具和特性,能够帮助我们更快速、更便捷地构建 Web 应用。在本文中,我们将会关注 Django 中的模型(Models)和数据库迁移(Database Migrations&#x…...
Chatgpt API调用报错:openai.error.RateLimitError
Chatgpt API 调用报错: openai.error.RateLimitError: You exceeded your current quota, please check your plan and billing details. 调用OpenAI API接口 import openai import osopenai.api_key os.getenv("OPENAI_API_KEY")result openai.Chat…...
一键获取数百张免费商用人脸!AI人脸生成器来袭
随着科技的发展,人工智能正在渗透到生活的各个角落,设计行业也不例外。在网页、APP、PPT 等界面设计中,设计师经常需要插入真实的人脸素材,以增强作品的真实感和场景化。但是获取素材既不容易,质量和价格也难免成为设计…...
跳跃游戏 II——力扣45
文章目录 题目描述解法一 贪心题目描述 解法一 贪心 int jump(vector<int>& nums){in...
谷歌浏览器插件
项目中有时候会用到插件 sync-cookie-extension1.0.0:开发环境同步测试 cookie 至 localhost,便于本地请求服务携带 cookie 参考地址:https://juejin.cn/post/7139354571712757767 里面有源码下载下来,加在到扩展即可使用FeHelp…...
全球首个30米分辨率湿地数据集(2000—2022)
数据简介 今天我们分享的数据是全球30米分辨率湿地数据集,包含8种湿地亚类,该数据以0.5X0.5的瓦片存储,我们整理了所有属于中国的瓦片名称与其对应省份,方便大家研究使用。 该数据集作为全球首个30米分辨率、覆盖2000–2022年时间…...
质量体系的重要
质量体系是为确保产品、服务或过程质量满足规定要求,由相互关联的要素构成的有机整体。其核心内容可归纳为以下五个方面: 🏛️ 一、组织架构与职责 质量体系明确组织内各部门、岗位的职责与权限,形成层级清晰的管理网络…...
Qt Http Server模块功能及架构
Qt Http Server 是 Qt 6.0 中引入的一个新模块,它提供了一个轻量级的 HTTP 服务器实现,主要用于构建基于 HTTP 的应用程序和服务。 功能介绍: 主要功能 HTTP服务器功能: 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个生活电费的缴纳和查询小程序
一、项目初始化与配置 1. 创建项目 ohpm init harmony/utility-payment-app 2. 配置权限 // module.json5 {"requestPermissions": [{"name": "ohos.permission.INTERNET"},{"name": "ohos.permission.GET_NETWORK_INFO"…...
tree 树组件大数据卡顿问题优化
问题背景 项目中有用到树组件用来做文件目录,但是由于这个树组件的节点越来越多,导致页面在滚动这个树组件的时候浏览器就很容易卡死。这种问题基本上都是因为dom节点太多,导致的浏览器卡顿,这里很明显就需要用到虚拟列表的技术&…...
AI+无人机如何守护濒危物种?YOLOv8实现95%精准识别
【导读】 野生动物监测在理解和保护生态系统中发挥着至关重要的作用。然而,传统的野生动物观察方法往往耗时耗力、成本高昂且范围有限。无人机的出现为野生动物监测提供了有前景的替代方案,能够实现大范围覆盖并远程采集数据。尽管具备这些优势…...
scikit-learn机器学习
# 同时添加如下代码, 这样每次环境(kernel)启动的时候只要运行下方代码即可: # Also add the following code, # so that every time the environment (kernel) starts, # just run the following code: import sys sys.path.append(/home/aistudio/external-libraries)机…...
DBLP数据库是什么?
DBLP(Digital Bibliography & Library Project)Computer Science Bibliography是全球著名的计算机科学出版物的开放书目数据库。DBLP所收录的期刊和会议论文质量较高,数据库文献更新速度很快,很好地反映了国际计算机科学学术研…...
6个月Python学习计划 Day 16 - 面向对象编程(OOP)基础
第三周 Day 3 🎯 今日目标 理解类(class)和对象(object)的关系学会定义类的属性、方法和构造函数(init)掌握对象的创建与使用初识封装、继承和多态的基本概念(预告) &a…...
