彻底搞懂0-1背包问题(动态规划)

彻底搞懂0-1背包问题(动态规划)看了很多网上的博客,发现对于0-1背包问题很多讲的都很专业,初学者学起来还是比较吃力,今天我就用最简单最形象的语言来描述一下0-1背包问题,为什么不能用贪婪算法,而要选择使用动态规划。首先对于0-1背包问题,我们需要知道的是:每一个物品只有1个,要么全拿,要么不拿,最后使得拿到的物品的总价值最大。假如一个小偷有一个可以容纳4千克的背包,但是发现面前只有有3样物品可以偷:台灯(30元,4千克)、音响(20元,3千克)、充电宝(15元,1千克)(价格和重量可能有点奇怪????)。问,小偷能够偷到的物品的

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

看了很多网上的博客,发现对于0-1背包问题很多讲的都很专业,初学者学起来还是比较吃力,今天我就用最简单最形象的语言来描述一下0-1背包问题,为什么不能用贪婪算法,而要选择使用动态规划。

  • 首先对于0-1背包问题,我们需要知道的是:每一个物品只有1个,要么全拿,要么不拿,最后使得拿到的物品的总价值最大。
  • 假如一个小偷有一个可以容纳4千克的背包,但是发现面前只有有3样物品可以偷:台灯(30元,4千克)、音响(20元,3千克)、充电宝(15元,1千克)(价格和重量可能有点奇怪?)。问,小偷能够偷到的物品的最大价格是多少(物品的重量不得超过背包的重量)?
    在这里插入图片描述
贪婪算法(不适用!!!)
  • 如果我们使用贪婪算法,每次都拿最贵的物品,那么我们可以看到:一开始拿到的是最贵的台灯,但是此时小偷已经拿到了4千克的重量,刚好把背包填充满了,无法再去偷第二个物品,那么此时获得的最大价值就是30元。但是我们发现如果偷音响和充电宝,可以获得的最大价值就是35元,明显比投台灯获得价值大。 所以贪婪算法在这里是不适用的!
动态规划
  • 动态规划的问题,一般是先解决子问题,然后由子问题推导,逐步解决大问题,所以我们可以先解决1千克的背包能够获得的最大价值,2千克的背包能够获得的最大价值,直到4千克的背包能够获得的最大价值。首先我们先搞定状态以及转移方程。我们这里定义状态f[i][v],表示前i件物品恰好放入一个容量为v的背包可以获得的最大价值。仔细想一下,我现在获得的最大价值可以建立在第 i 个物品我不偷,那重量是v;也可以是第 i 个物品我偷了,那么前 i-1 个物品的总重量是 v-c[i] ,再加上我现在准备偷的第 i 个物品的价值 v[i],取两者的最大值即可。那么,转移方程就是: f [ i [ [ v ] = m a x ( f [ i − 1 ] [ v ] , f [ i − 1 ] [ v − c [ i ] ] + v [ i ] ) f[i[[v] = max(f[i-1][v],f[i-1][v-c[i]]+v[i]) f[i[[v]=max(f[i1][v],f[i1][vc[i]]+v[i])
  • 听起来挺抽象的,接下来我们可以用一个网格来描述(每一个单元格都包含当前可装入背包的所有物品):在这里插入图片描述
  1. 然后我们开始遍历这个网格,一开始我们填充台灯这一行。发现,当背包的容量为1千克的时候,由于台灯的重量是4千克,所以偷不了,所以此时获得的最大价值为0元。
    在这里插入图片描述
    直到背包的容量为4千克的时候,我们才可以偷台灯,此时获得的最大价值为30元。
    在这里插入图片描述
  2. 接下来我们开始遍历音响这一行,现在可以偷的物品有台灯和音响(每一行可以偷的物品只有当前行以及前一行的物品),同样的,发现直到背包的容量是3千克的时候才能装的下音响。在这里插入图片描述
    当背包的重量是4千克的时候,我们要么只能偷台灯,要么只能偷音响,发现偷台灯的价值会更大一点,所以我们选择偷台灯。在这里插入图片描述
  3. 最后我们来遍历充电宝这一行,发现当背包重量为1千克和2千克的时候,我们只能容纳充电宝,所以获得的最大价值为15元。在这里插入图片描述
    当背包容量为3千克时候,我们可以获得的最大价值就是偷了音响,20元。在这里插入图片描述
    当背包容量为4千克的时候,我们可以不偷充电宝,那么直接由上一行获得的最大价值传递过来,就是30元;我们也可以偷充电宝,那么要偷充电宝的话就只剩下3千克的背包容量了,在3千克的背包容量时能够获得的最大价值是20元,所以最后获得的最大价值为35元。两种情况比较,取最大值,所以最后小偷获得的最大价值为35元。在这里插入图片描述
  4. 对于这个0-1背包问题,如果我们再增加一件物品,可以继续如此推导下去。如果我们偷的物品的顺序不一样(比如先偷音响,再偷台灯,再偷充电宝),也不会影响到最终的结果。
  • 最后想说的是,如果小偷可以偷一个物品的某一部分,比如可以偷一袋米的一部分米,那么动态规划在这里就不适用了,反而可以用贪心算法实现。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/164410.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • pycharm导入pandas模块_pycharm如何导入python的库

    pycharm导入pandas模块_pycharm如何导入python的库pycharm上安装库(以pandas为例)网上有些反应安装pandas库时会出现问题,提示好像是pip的原因。这时候大概是自己的pip版本太久啦。所以最好先在cmd更新一下pip好了。在cmd输入命令:python-mpipinstall-Upip出现成功信息:Requirementalreadyup-to-date即可。之后打开pycharm1、点击右上角file/se

  • 02-Epicor二次开发常用代码

    02-Epicor二次开发常用代码二次开发,俗称客制。是程序员根据需求,进入开发模式对Epicor进行代码修改。1、获取到的完整的SQL,可以将SQL语句弹出来2、每个公司的代码是一样的,不一样请清理系统缓存,并退出系统重新进入3、隐藏一列4、关于界面居中问题5、测试跟正式的水晶报表文件都在192.168.100.250的EpicorData\CustomReports文件夹中6、关于报表位置不够问题7、将DataView的数据转化为xml的文件,用于更新水晶报表8、vb.net中换行…

  • hikaripool信息_HikariPool源码(四)资源状态[通俗易懂]

    hikaripool信息_HikariPool源码(四)资源状态[通俗易懂]Java极客|作者/铿然一叶这是Java极客的第55篇原创文章1.本章目的了解池资源的状态,以及状态如何变迁,用于池化资源设计参考。2.HikariPool资源核心类回顾HikariPool资源相关的类如下:类说明:类职责HikariPool资源池,客户端资源操作的入口。ConcurrentBag通用的并发包工具。CopyOnWriteArrayList一个列表,用于存储资源,…

  • php behaviors,YII框架行为behaviors用法示例[通俗易懂]

    php behaviors,YII框架行为behaviors用法示例[通俗易懂]本文实例讲述了YII框架行为behaviors用法。分享给大家供大家参考,具体如下:文件frontend/libs/FilterTest.php/***CreatedbyPhpStorm.*Date:2016/5/27*Time:14:16*/namespacefrontend\libs;useYii;useyii\base\Action;useyii\base\Actio…

    2022年10月26日
  • 极客日报第 26 期:华大基因辟谣“基因编辑58个婴儿”;苹果发布头戴式耳机AirPods Max

    极客日报第 26 期:华大基因辟谣“基因编辑58个婴儿”;苹果发布头戴式耳机AirPods Max文章目录互联网快讯程序员专属Github每日精选CSDN社区优质博文精选互联网快讯1、我国一项物联网安全测试技术成为国际标准从WAPI产业联盟获悉,我国自主研发的一项物联网安全测试技术(TRAIS-PTEST)日前由国际标准化组织/国际电工委员会(ISO/IEC)发布成为国际标准。据介绍,该标准是TRAIS-P国际标准的测试标准,它规范了无线射频识别(RFID)安全密码套件一致性测试方法。标准发布后,将从技术到产品测试两个层面共同构成国际标准体系。(新华社)2、百度百科:日均搜索超4亿人次据.

  • mysql数据类型有哪几种_数据库 数据类型

    mysql数据类型有哪几种_数据库 数据类型Mysql支持的多种数据类型主要有:数值数据类型、日期/时间类型、字符串类型。整数浮点数&定点数注:定点数以字符串形式存储,对精度要求高时使用decimal较好;尽量避免对浮点数进行减法和比较运算。时间/日期类型字符串类型blog-二进制大对象,用来存储可变数量的数据。…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号