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

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背包问题及变种详解_理学_高等教育_教育专区。经典的背包问题九讲文档,包含了...其方程的 意义以及如何得来,是加深对动态规划的理解、提高动态规划功力的方法...
背包问题题目及含义
DD 牛的背包九讲 P01: 01 背包问题 题目 有 N ...所以有 必要将它详细解释一下:“将前 i 件物品...是加深对动态规划的理解、 提高动态规划功力的方法...
01背包代码及分析
01背包代码及分析_信息与通信_工程科技_专业资料。01背包代码及分析,超级详细0/1 背包问题动态规划详解及 C 代码 背包问题动态规划详解及 动态规划详动态规划是用...
01背包
摘自 Tianyi Cui 童鞋的《背包问题九讲》,稍作修改,方便理解01 背包问题...智商啊 作者说,当 V 很大是,效果好。 代码 [cpp] view plain copy 1. 2...
01背包问题动态规划详解
01背包问题动态规划详解_计算机软件及应用_IT/计算机_专业资料。01背包问题动态...为什么呢?可以这样理解: 初始化的 f 数组事实上就是在没有任何物品可以放入 ...
背包详解
背包之 01 背包、完全背包、多重背包详解 BY TANKY...请大家具体还是好好看看 dd 大牛的 《背包九讲》...如果不太理解的话,不妨翻译成程序代码以后,单 步...
算法实验报告01背包问题
算法实验报告01背包问题_工学_高等教育_教育专区。hebut...本实验加深对贪心算法、动态规划和回溯算法的理解。 ...0-1背包问题动态规划详解... 4页 免费 0-1背包...
01背包问题论文
01背包问题论文_计算机软件及应用_IT/计算机_专业资料。01背包问题论文 ,贪心算法...return 0; } 4.结果截图 6.参考文献 首先鸣谢百度知道的达人给与的错误讲解。...
01背包问题
01背包问题详解 8页 5财富值 01背包问题题解 6页 1财富值 经典的01背包问题...理解算法思想和问题要求; A:0-1 背包问题:给定 n 种物品和一背包。物品 i ...
遗传算法解决01背包问题
遗传算法解决01背包问题_计算机硬件及网络_IT/计算机...高度非 线形的不连续多峰函数的优化以及无解析...能克服传统优化方法的 缺点,从而达到好的优化效果。...
更多相关标签:
哪个牌子的背包比较好 | 背包什么牌子比较好 | 什么背包比较好 | 比较好的背包品牌 | 背包那个牌子比较好 | 讲解汽轮机比较好视频 | c 完全背包讲解 | 背包问题讲解 |