下载文档原格式
01背包问题，是用来介绍动态规划算法最经典的例子，网上关于01背包问题的讲解也很多，我写这篇文章力争做到用最简单的方式，最少的公式把01背包问题讲解透彻。
01背包的状态转换方程f[i,j] = Max{ f[i-1,j-Wi]+Pi( j >= Wi ), f[i-1,j] }只要你能通过找规律手工填写出上面这张表就算理解了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 的代码public function get01PackageAnswer(bagItems:Array,bagSize:int):Array{var bagMatrix:Array=[];var i:int;var item:PackageItem;for(i=0;i<bagItems.length;i++){bagMatrix[i] = [0];}for(i=1;i<=bagSize;i++){for(varj:int=0;j<bagItems.length;j++){item = bagItems[j] as PackageItem;if(item.weight > i){//i背包转不下itemif(j==0){bagMatrix[j][i] = 0;}else{bagMatrix[j][i]=bagMatrix[j-1][i];}}else{//将item装入背包后的价值总和var itemInBag: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 answervar answers:Array=[];var curSize: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();break;}if(bagMatrix[i][curSize]-bagMatrix[i-1][curSize-item.weight ]==item.value){answers.push();curSize -= item.weight;}}return answers;}PackageItem类public class PackageItem{public var name:String;public var weight:int;public var value:int;public function PackageItem(name:String,weight:int,value:int){ = name;this.weight = weight;this.value = value;}}测试代码varnameArr:Array=['a','b','c','d','e'];var weightArr:Array=[2,2,6,5,4];var valueArr:Array=[6,3,5,4,6];var bagItems:Array=[];for(vari:int=0;i<nameArr.length;i++){var bagItem:PackageItem = new PackageItem(nameArr[i],weightArr[i],valueArr[i]);bagItems[i]=bagItem;}var arr:Array = ac.get01PackageAnswer(bagItems,10);。
背包问题常州一中林厚从背包问题是信息学奥赛中的经典问题。
背包问题可以分为0-1背包和部分背包两种类型，0-1背包还可以再分为有限背包和无限背包（完全背包）。
背包问题的求解涉及到贪心、递归、递推、动态规划、搜索等多种算法。
熟练掌握各种背包问题及其变形试题的解法，是信息学奥赛选手从入门走向提高的必经之路。
先简单归纳一下涉及到的这几种重要算法：1、贪心：贪心法可以归纳为“每步取优”。
假设你的程序要走1~n共n步，则你只要保证在第i步（i=1..n）时走出的这一步是最优的。
所以，贪心法不是穷举，而只是一种每步都取优的走法。
但由于目光短浅，不考虑整体和全局，所以“步步最优”并不能保证最后的结果最优。
比如经典的“两头取数”问题、“n个整数连接成最大数”问题、“删数”问题等。
2、递归：递归算法可以归纳为将问题“由大化小”。
也就是将一个大问题分解为若干个“性质相同”的子问题，求解的的过程，一般是通过“函数的递归调用”，不断将大问题逐步细化、直至元问题（边界情况），最后通过递归函数的自动返回得到问题的解。
递归算法的关键是递归函数的构造，它的效率往往比较低，原因在于大量的“冗余”计算。
比如经典的“斐波那挈数列”问题，在递归实现时效率极低，存在着大量的冗余计算，可以采用“记忆化”的方法优化。
3、递推：递推问题往往有一个“递推公式”，其实和“递归公式”差不多，但是出发点不一样，递归的思想是“要想求什么就要先求出什么”。
而递推是从问题的边界情况（初始状态）出发，一步步往下走，直到走完n步，判断最后的解。
由于其中的每一步并不知道当前一步的哪一个值对后面的步骤有用，所以只能把所有情况（一步的所有走法）全部计算出来，也造成了很多的“冗余计算”。
时间上往往没有太多的优化余地，但空间上经常利用“滚动数组”等方式，把空间复杂度由O（n2）降到O（2n）。
比如经典的“杨辉三角形”问题、“判断n是否是斐波那挈数”问题等。
4、动态规划：本质上是一种克服了“冗余”的“递归”算法。
