当前位置:首页 >> 学科竞赛 >>

01背包较好理解的讲解


动态规划之 01 背包问题(最易理解的讲解) 分类: 01 背包动态规划 2012-07-06 17:09 31770 人阅读评论(13) 收藏举报 算法 c 01 背包问题, 是用来介绍动态规划算法最经典的例子, 网上关于 01 背包问题的讲解也很多, 我写这篇文章力争做到用最简单的方式,最少的公式把 01 背包问题讲解透彻。 01 背包的状态转换方程 f[i,j] = Max

{ f[i-1,j-Wi]+Pi( j >= Wi ), f[i-1,j] } f[i,j]表示在前 i 件物品中选择若干件放在承重为 j 的背包中,可以取得的最大价值。 Pi 表示第 i 件物品的价值。 决策:为了背包中物品总价值最大化,第 i 件物品应该放入背包中吗? 题目描述: 有编号分别为 a,b,c,d,e 的五件物品, 它们的重量分别是 2,2,6,5,4, 它们的价值分别是 6,3,5,4,6, 现在给你个承重为 10 的背包,如何让背包里装入的物品具有最大的价值总和?

name a b c d e

weight 2 2 6 5 4

value 6 3 5 4 6

1 0 0 0 0 0

2 6 3 0 0 0

3 6 3 0 0 0

4 9 6 6 6 6

5 9 6 6 6 6

6 12 9 6 6 6

7 12 9 6 6 6

8 15 9 6 6 6

9 15 10 10 10 6

10 15 11 11 10 6

只要你能通过找规律手工填写出上面这张表就算理解了 01 背包的动态规划算法。 首先要明确这张表是至底向上,从左到右生成的。 为了叙述方便,用 e2 单元格表示 e 行 2 列的单元格,这个单元格的意义是用来表示只有物 品 e 时,有个承重为 2 的背包,那么这个背包的最大价值是 0,因为 e 物品的重量是 4,背 包装不了。 对于 d2 单元格,表示只有物品 e,d 时,承重为 2 的背包,所能装入的最大价值,仍然是 0, 因为物品 e,d 都不是这个背包能装的。 同理,c2=0,b2=3,a2=6。 对于承重为 8 的背包,a8=15,是怎么得出的呢? 根据 01 背包的状态转换方程,需要考察两个值, 一个是 f[i-1,j],对于这个例子来说就是 b8 的值 9,另一个是 f[i-1,j-Wi]+Pi; 在这里,

f[i-1,j]表示我有一个承重为 8 的背包,当只有物品 b,c,d,e 四件可选时,这个背包能装入的 最大价值 f[i-1,j-Wi]表示我有一个承重为 6 的背包(等于当前背包承重减去物品 a 的重量) ,当只有物 品 b,c,d,e 四件可选时,这个背包能装入的最大价值 f[i-1,j-Wi]就是指单元格 b6,值为 9,Pi 指的是 a 物品的价值,即 6 由于 f[i-1,j-Wi]+Pi = 9 + 6 = 15 大于 f[i-1,j] = 9,所以物品 a 应该放入承重为 8 的背包 以下是 actionscript3 的代码 [java] view plaincopy 在 CODE 上查看代码片派生到我的代码片 public function get01PackageAnswer(bagItems:Array,bagSize:int):Array { varbagMatrix:Array=[]; var i:int; varitem:PackageItem; for(i=0;i<bagItems.length;i++) { bagMatrix[i] = [0]; } for(i=1;i<=bagSize;i++) { for(var j:int=0;j<bagItems.length;j++) { item = bagItems[j] as PackageItem; if(item.weight>i) { //i 背包转不下 item if(j==0) { bagMatrix[j][i] = 0; } else { bagMatrix[j][i]=bagMatrix[j-1][i]; } } else { //将 item 装入背包后的价值总和 varitemInBag:int;

if(j==0) { bagMatrix[j][i] = item.value; continue; } else { itemInBag = bagMatrix[j-1][i-item.weight]+item.value; } bagMatrix[j][i] = (bagMatrix[j-1][i] >itemInBag ? bagMatrix[j-1][i] : itemInBag) } } } //find answer varanswers:Array=[]; varcurSize:int = bagSize; for(i=bagItems.length-1;i>=0;i--) { item = bagItems[i] as PackageItem; if(curSize==0) { break; } if(i==0 &&curSize> 0) { answers.push(item.name); break; } if(bagMatrix[i][curSize]-bagMatrix[i-1][curSize-item.weight]==item.value) { answers.push(item.name); curSize -= item.weight; } } return answers; }

PackageItem 类 [java] view plaincopy 在 CODE 上查看代码片派生到我的代码片

public class PackageItem { publicvarname:String; publicvarweight:int; publicvarvalue:int; public function PackageItem(name:String,weight:int,value:int) { this.name = name; this.weight = weight; this.value = value; } }

测试代码 [java] view plaincopy 在 CODE 上查看代码片派生到我的代码片 varnameArr:Array=['a','b','c','d','e']; varweightArr:Array=[2,2,6,5,4]; varvalueArr:Array=[6,3,5,4,6]; varbagItems:Array=[]; for(var i:int=0;i<nameArr.length;i++) { varbagItem:PackageItem = new PackageItem(nameArr[i],weightArr[i],valueArr[i]); bagItems[i]=bagItem; } vararr:Array = ac.get01PackageAnswer(bagItems,10);


相关文章:
01背包较好理解的讲解
01背包较好理解的讲解_学科竞赛_高中教育_教育专区。动态规划之 01 背包问题(最易理解的讲解) 分类: 01 背包动态规划 2012-07-06 17:09 31770 人阅读评论(13...
动态规划之01背包问题(最易理解的讲解)
动态规划之01背包问题(最易理解的讲解)_天文/地理_自然科学_专业资料。01 背包问题,是用来介绍动态规划算法最经典的例子,网上关于 01 背包问题的 讲解也很多,我写...
01背包详解
大家可以根 据数据自己推一下这张表,以加深理解。 具体的状态转移方程请参考 PPT。 01 背包的两个性质 性质 1 dp[i][j]的值一定是由集合{dp[a][b] | ...
背包九讲之01背包详解
背包之01背包、完全背包... 6页 2下载券 01背包问题及变种详解 18页 1下载...“恰好装满背包”时的最优解, 那么在初始化时除了 f[0]为 0 其它 f[1.....
经典的01背包问题
这篇文章就是为了帮助大家理解动态规划,并通过讲解基本的 01 背包问题来引导读者...思考动态规划的第二点---子问题重叠: 实际上国王也好,大臣也好,所有人面对的...
01背包的讲解
01背包的讲解 (动态规划资料)DP(动态规划资料)DP隐藏>> 动态规划是用空间换时间...理解上述记忆体的过程: f(2,4) 从 f(1,4) 上一个状态下没有给它预留...
算法设计-01背包问题的分析
算法设计-01背包问题的分析_工学_高等教育_教育专区...[i]} for v=V..bound 这对于 V 比较大时是...六、0/1 背包实例为了进一步的理解 0/1 背包问题...
01背包问题详解
背包九讲之01背包详解 暂无评价 7页 免费 01背包的讲解 暂无评价 2页 免费喜欢...背包问题详解 44页 2下载券 解决01背包问题算法比较 30页 1下载券 冶金物理化...
01背包问题不同算法设计、分析与对比
实验三 01 背包问题不同算法设计、分析与对比一.问题描述给定 n 种物品和一...贪 心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考...
01背包问题及变种详解
01背包问题及变种详解_理学_高等教育_教育专区。经典...后面也就不再对进行状态转移 之前的初始化进行讲解...是加深对动态规划的理解、提高动态规划功力的方法...
更多相关标签:
怎么理解01背包问题 | 哪个牌子的背包比较好 | 背包什么牌子比较好 | 比较好的背包品牌 | 什么背包比较好 | 什么牌子的背包比较好 | 比较好的背包 | 古诗词怎样讲解比较好 |