当前位置: 首页 > news >正文

动态规划解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背包问题(超详细理解)

前言&#xff1a; 好久没写0-1背包问题了&#xff0c;都有些不记得了&#xff0c;写这篇文章给自己以后做简单参考&#xff0c;如果能同时帮到读者&#xff0c;不胜荣幸。 正文 0-1背包问题是这样的一个问题&#xff0c;假设有一个背包&#xff0c;其容量为 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优化选项&#xff0c;可在编译时间&#xff0c;目标文件长度&#xff0c;执行效率三个维度&#xff0c;进行不同的取舍和平衡。 gcc 常用编译选项 arm-linux-gnueabihf-g -O3 -marcharmv7-a -mcpucortex-a9 -ftree-vectorize -mfpuneon -mfpuvfpv3-fp16 -mfloat-abihard -…...

vmwera中安装的centos8出现ifconfig不可用

刚刚在虚拟机中装好centos结果发现自己的ifconfig命令不可用。 看一下环境变量里有没有ifconfig命令的路径&#xff0c;因为ifconfig是在/sbin路径下的&#xff0c;root用户登录进去才可以运行&#xff0c;先看一下root用户的环境变量。 root用户的环境变量里是有/sbin路径的&a…...

线性表中的时间复杂度

线性表 一、顺序表示的线性表 插入操作的时间复杂度 最好情况&#xff1a; O ( 1 ) O(1) O(1)。&#xff08;新元素插到表尾&#xff0c;不需要移动元素&#xff09;最坏情况&#xff1a; O ( n ) O(n) O(n)。&#xff08;新元素插到表头&#xff0c;需要将原有的n个元素全部…...

ensp与虚拟机搭建测试环境

1.虚拟机配置 ①首先确定VMnet8 IP地址&#xff0c;若要修改IP地址&#xff0c;保证在启动Ensp前操作 ②尽量保证NAT模式 2.ensp配置 (1)拓扑结构 (2)Cloud配置 ①首先点击 绑定信息 UDP → 增加 ②然后点击 绑定信息 VMware ... → 增加 ③最后在 端口映射设置上点击双向通…...

linux内核中的 指针 和 unsigned long

文章目录 1.指针的来源2.指针的定义&#xff1a;3.字长和数据类型4.Linux内核为什么常用unsigned long来替代指针&#xff1f;参考资料 1.指针的来源 方便引用一个内存地址。 给定一个内存地址&#xff0c;CPU就可以取出该地址的数据。 给定一个内存地址&#xff0c;CPU就可以…...

STM32--GPIO

文章目录 GPIO简介GPIO的基本结构GPIO位结构GPIO模式LED和蜂鸣器LED闪烁工程及程序原码代码&#xff1a; 蜂鸣器工程和程序原码代码 传感器光敏传感器控制蜂鸣器工程代码 GPIO简介 GPIO&#xff08;General Purpose Input Output&#xff09;是通用输入/输出口的简称。它是一种…...

剑指 Offer ! 61. 扑克牌中的顺子

参考资料&#xff1a;力扣K神的讲解 剑指 Offer 61. 扑克牌中的顺子 简单 351 相关企业 从若干副扑克牌中随机抽 5 张牌&#xff0c;判断是不是一个顺子&#xff0c;即这5张牌是不是连续的。2&#xff5e;10为数字本身&#xff0c;A为1&#xff0c;J为11&#xff0c;Q为12&…...

《玩转Python数据分析专栏》大纲

欢迎来到《玩转Python数据分析分类专栏》!在这个专栏中,我们将带您深入探索数据分析的世界,以Python为工具,解析各个领域的实际应用场景。通过100篇教程,我们将逐步引领您从入门级到高级,从基础知识到实战技巧,助您成为一名优秀的数据分析师。 专栏目标 本专栏旨在帮助…...

Zabbix自动注册服务器及部署代理服务器

文章目录 一.zabbix自动注册1.什么是自动注册2.环境准备3.zabbix客户端配置4.在 Web 页面配置自动注册5.验证自动注册 二.部署 zabbix 代理服务器1.分布式监控的作用&#xff1a;2.环境部署3.代理服务器配置4.客户端配置5.web页面配置5.1 删除原来配置5.2 添加代理5.3 创建主机…...

SpringBoot下使用自定义监听事件

事件机制是Spring的一个功能&#xff0c;目前我们使用了SpringBoot框架&#xff0c;所以记录下事件机制在SpringBoot框架下的使用&#xff0c;同时实现异步处理。事件机制其实就是使用了观察者模式(发布-订阅模式)。 Spring的事件机制经过如下流程&#xff1a; 1、自定义事件…...

并发编程面试题1

并发编程面试题1 一、原子性高频问题&#xff1a; 1.1 Java中如何实现线程安全? 多线程操作共享数据出现的问题。 锁&#xff1a; 悲观锁&#xff1a;synchronized&#xff0c;lock乐观锁&#xff1a;CAS 可以根据业务情况&#xff0c;选择ThreadLocal&#xff0c;让每个…...

【对于一维信号的匹配】对一个一维(时间)信号y使用自定义基B执行匹配追踪(MP)研究(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…...

【Oracle 数据库 SQL 语句 】积累1

Oracle 数据库 SQL 语句 1、分组之后再合计2、显示不为空的值 1、分组之后再合计 关键字&#xff1a; grouping sets &#xff08;&#xff08;分组字段1&#xff0c;分组字段2&#xff09;&#xff0c;&#xff08;&#xff09;&#xff09; select sylbdm ,count(sylbmc) a…...

Django中级指南:理解并实现Django的模型和数据库迁移

Django 是一个极其强大的 Python Web 框架&#xff0c;它提供了许多工具和特性&#xff0c;能够帮助我们更快速、更便捷地构建 Web 应用。在本文中&#xff0c;我们将会关注 Django 中的模型&#xff08;Models&#xff09;和数据库迁移&#xff08;Database Migrations&#x…...

Chatgpt API调用报错:openai.error.RateLimitError

Chatgpt API 调用报错&#xff1a; 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人脸生成器来袭

随着科技的发展&#xff0c;人工智能正在渗透到生活的各个角落&#xff0c;设计行业也不例外。在网页、APP、PPT 等界面设计中&#xff0c;设计师经常需要插入真实的人脸素材&#xff0c;以增强作品的真实感和场景化。但是获取素材既不容易&#xff0c;质量和价格也难免成为设计…...

跳跃游戏 II——力扣45

文章目录 题目描述解法一 贪心题目描述 解法一 贪心 int jump(vector<int>& nums){in...

Opencv中的addweighted函数

一.addweighted函数作用 addweighted&#xff08;&#xff09;是OpenCV库中用于图像处理的函数&#xff0c;主要功能是将两个输入图像&#xff08;尺寸和类型相同&#xff09;按照指定的权重进行加权叠加&#xff08;图像融合&#xff09;&#xff0c;并添加一个标量值&#x…...

Python实现prophet 理论及参数优化

文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候&#xff0c;写过一篇简单实现&#xff0c;后期随着对该模型的深入研究&#xff0c;本次记录涉及到prophet 的公式以及参数调优&#xff0c;从公式可以更直观…...

【JavaWeb】Docker项目部署

引言 之前学习了Linux操作系统的常见命令&#xff0c;在Linux上安装软件&#xff0c;以及如何在Linux上部署一个单体项目&#xff0c;大多数同学都会有相同的感受&#xff0c;那就是麻烦。 核心体现在三点&#xff1a; 命令太多了&#xff0c;记不住 软件安装包名字复杂&…...

ABAP设计模式之---“简单设计原则(Simple Design)”

“Simple Design”&#xff08;简单设计&#xff09;是软件开发中的一个重要理念&#xff0c;倡导以最简单的方式实现软件功能&#xff0c;以确保代码清晰易懂、易维护&#xff0c;并在项目需求变化时能够快速适应。 其核心目标是避免复杂和过度设计&#xff0c;遵循“让事情保…...

Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析

Java求职者面试指南&#xff1a;Spring、Spring Boot、MyBatis框架与计算机基础问题解析 一、第一轮提问&#xff08;基础概念问题&#xff09; 1. 请解释Spring框架的核心容器是什么&#xff1f;它在Spring中起到什么作用&#xff1f; Spring框架的核心容器是IoC容器&#…...

C++.OpenGL (14/64)多光源(Multiple Lights)

多光源(Multiple Lights) 多光源渲染技术概览 #mermaid-svg-3L5e5gGn76TNh7Lq {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-3L5e5gGn76TNh7Lq .error-icon{fill:#552222;}#mermaid-svg-3L5e5gGn76TNh7Lq .erro…...

Java数值运算常见陷阱与规避方法

整数除法中的舍入问题 问题现象 当开发者预期进行浮点除法却误用整数除法时,会出现小数部分被截断的情况。典型错误模式如下: void process(int value) {double half = value / 2; // 整数除法导致截断// 使用half变量 }此时...

Qemu arm操作系统开发环境

使用qemu虚拟arm硬件比较合适。 步骤如下&#xff1a; 安装qemu apt install qemu-system安装aarch64-none-elf-gcc 需要手动下载&#xff0c;下载地址&#xff1a;https://developer.arm.com/-/media/Files/downloads/gnu/13.2.rel1/binrel/arm-gnu-toolchain-13.2.rel1-x…...

【java面试】微服务篇

【java面试】微服务篇 一、总体框架二、Springcloud&#xff08;一&#xff09;Springcloud五大组件&#xff08;二&#xff09;服务注册和发现1、Eureka2、Nacos &#xff08;三&#xff09;负载均衡1、Ribbon负载均衡流程2、Ribbon负载均衡策略3、自定义负载均衡策略4、总结 …...

云原生安全实战:API网关Envoy的鉴权与限流详解

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、基础概念 1. API网关 作为微服务架构的统一入口&#xff0c;负责路由转发、安全控制、流量管理等核心功能。 2. Envoy 由Lyft开源的高性能云原生…...