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

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背包、完全背包... 6页 2下载券 01背包问题及变种详解 18页 1下载...“恰好装满背包”时的最优解, 那么在初始化时除了 f[0]为 0 其它 f[1.....
01背包的讲解
01背包的讲解 (动态规划资料)DP(动态规划资料)DP隐藏>> 动态规划是用空间换时间...理解上述记忆体的过程: f(2,4) 从 f(1,4) 上一个状态下没有给它预留...
01背包问题详解
背包九讲之01背包详解 暂无评价 7页 免费 01背包的讲解 暂无评价 2页 免费喜欢...背包问题详解 44页 2下载券 解决01背包问题算法比较 30页 1下载券 冶金物理化...
01背包问题不同算法设计、分析与对比
实验三 01 背包问题不同算法设计、分析与对比一.问题描述给定 n 种物品和一...贪 心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考...
01背包详解包含路径输出
背包问题——“01 背包”详解及实现 (包含背包中具体物品的求解)分类: 背包问题 2011-11-26 14:41 9554 人阅读 评论(10) 收藏举报 pathtabledelete 测试 c ...
01背包问题及变种详解
01背包问题及变种详解_理学_高等教育_教育专区。经典...后面也就不再对进行状态转移 之前的初始化进行讲解...是加深对动态规划的理解、提高动态规划功力的方法...
01背包问题
01背包问题_计算机软件及应用_IT/计算机_专业资料。01 背包问题其实这个问题不是...礼品数量有限,先抢先得! 马上抢已有 38660位 抢到好礼...
01背包问题
01背包问题_计算机硬件及网络_IT/计算机_专业资料。01背包问题,算法 习题二:0/1 背包问题 源代码: #include<iostream> using namespace std; int *answer;//...
01背包问题题解
P01: 01 背包问题题目有 N 件物品和一个容量为 ...是加深对动态规划的理解、提高动态规划功力的方法...DP 已超出了 NOIP 的范围,故本文不再展开讲解。我...
01背包问题
2页 2财富值 01背包问题代码 6页 5财富值如要投诉...理解算法思想和问题要求; A:0-1 背包问题:给定 n...时间效率比 较高,对于精度要求不是很高的情况比较...
更多相关标签:
01背包讲解 | 背包什么牌子比较好 | 哪个牌子的背包比较好 | 比较好的背包品牌 | 什么背包比较好 | 缠论讲解比较好的 | 男士背包比较好 | 国外比较好的背包皮牌 |