下载文档原格式
动态规划——01背包问题⼀、最基础的动态规划之⼀01背包问题是动态规划中最基础的问题之⼀，它的解法完美地体现了动态规划的思想和性质。
01背包问题最常见的问题形式是：给定n件物品的体积和价值，将他们尽可能地放⼊⼀个体积固定的背包，最⼤的价值可以是多少。
我们可以⽤费⽤c和价值v来描述⼀件物品，再设允许的最⼤花费为w。
只要n稍⼤，我们就不可能通过搜索来遍查所有组合的可能。
运⽤动态规划的思想，我们把原来的问题拆分为⼦问题，⼦问题再进⼀步拆分直⾄不可再分（初始值），随后从初始值开始，尽可能地求取每⼀个⼦问题的最优解，最终就能求得原问题的解。
由于不同的问题可能有相同的⼦问题，⼦问题存在⼤量重叠，我们需要额外的空间来存储已经求得的⼦问题的最优解。
这样，可以⼤幅度地降低时间复杂度。
有了这样的思想，我们来看01背包问题可以怎样拆分成⼦问题：要求解的问题是：在n件物品中最⼤花费为w能得到的最⼤价值。
显然，对于0 <= i <= n,0 <= j <= w，在前i件物品中最⼤花费为j能得到的最⼤价值。
可以使⽤数组dp[n + 1][w + 1]来存储所有的⼦问题，dp[i][j]就代表从前i件物品中选出总花费不超过j时的最⼤价值。
可知dp[0][j]值⼀定为零。
那么，该怎么递推求取所有⼦问题的解呢。
显⽽易见，要考虑在前i件物品中拿取，⾸先要考虑前i - 1件物品中拿取的最优情况。
当我们从第i - 1件物品递推到第i件时，我们就要考虑这件物品是拿，还是不拿，怎样收益最⼤。
①：⾸先，如果j < c[i]，那第i件物品是⽆论如何拿不了的，dp[i][j] = dp[i - 1][j];②：如果可以拿，那就要考虑拿了之后收益是否更⼤。
拿这件物品需要花费c[i]，除去这c[i]的⼦问题应该是dp[i - 1][j - c[i]]，这时，就要⽐较dp[i - 1][j]和dp[i - 1][j - c[i]] + v[i]，得出最优⽅案。
背包问题解析（⼀）-贪⼼算法⼀、题⽬:有N件物品和⼀个容量为V的背包。
第i件物品的重量是w[i]，价值是v[i]。
求解将哪些物品装⼊背包可使这些物品的重量总和不超过背包容量，且价值总和最⼤。
⼆、解决思路:本题刚开始的解题的时候,想采取贪⼼算法来解决,也就是将放⼊的物品的性价⽐按照从⾼到低进⾏排序，然后优先放优先级⾼的，其次优先级低的。
三、代码实现（python）1# 重量w=[5,4,3,2]2# 价值v=[6,5,4,3]3 b=[]4 m=int(input("请输⼊背包的最⼤重量:"))5 n=int(input("请输⼊商品的数量:"))6for i in range(n):7 a=input("请分别输⼊重量和价值,以空格隔开:")8 a=a.split("")9for i in range(len(a)):10 a[i]=int(a[i])11 b.append(a)12print("加载初始化:",b)13for i in range(len(b)):14for j in range(i+1,len(b)):15if b[i][1]/b[i][0]<b[j][1]/b[j][0]:16 b[i],b[j]=b[j],b[i]17print("性价⽐排序:",b)18 v=019 c=[]20for i in range(len(b)):21if m-b[i][0]>0:22 m=m-b[i][0]23 c.append(b[i])24 v+=b[i][1]25print("放⼊背包:",c)26print("最⼤价值为:",v)打印结果：四、算法分析：贪⼼选择是指所求问题的整体最优解可以通过⼀系列局部最优的选择，即贪⼼选择来达到。
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);。
利用动态规划解决01背包问题01背包问题动态规划背包问题是一个经典的动态规划模型,很多关于算法的教材都把它作为一道例题,该问题既简单又容易理解,而且在某种程度上还能够揭示动态规划的本质。
将具有不同重量和价值的物体装入一个有固定载重量的背包,以获取最大价值,这类问题被称为背包问题。
背包问题可以扩展出很多种问题,而01背包问题是最常见、最有代表性的背包问题。
一、问题描述给定一个载重量为M的背包及n个物体,物体i的重量为wi、价值为pi,1≤i≤n,要求把这些物体装入背包,使背包内的物体价值总量最大。
此处我们讨论的物体是不可分割的,通常称这种物体不可分割的背包问题为01背包问题。
二、基本思路01背包问题的特点是:每种物体只有一件,可以选择放或者不放。
假设:xi表示物体i被装入背包的情况,xi=0,1。
当xi=0时,表示物体没有被装入背包;当xi=1时,表示物体被装入背包。
根据问题的要求,有如下的约束方程(1)和目标函数(2):三、利用动态规划法求解01背包问题(一)动态规划算法的基本思想动态规划算法通常用于求解具有某种最优性质的问题。
在这类问题中,可能会有许多可行解。
每一个解都对应于一个值,我们希望找到具有最优值的解。
动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。
与分治法不同的是,适合于用动态规划求解的问题,经分解得到子问题往往不是互相独立的。
若用分治法来解这类问题,则分解得到的子问题数目太多,有些子问题被重复计算很多次。
如果我们能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,这样就可以避免大量的重复计算,节省时间。
我们可以用一个表来记录所有已解的子问题的答案。
不管该子问题以后是否被用到,只要它被计算过,就将其结果填入表中,这就是动态规划法的基本思路。
具体的动态规划算法多种多样,但它们具有相同的填表格式。
(二)算法设计假定背包的载重量范围为0～m。
数据结构背包问题【数据结构背包问题】【背景介绍】背包问题是一类经典的组合优化问题，通过在给定的一组物品中选择一些物品放入背包，以使得放入背包的物品总价值最大或总重量最小。
【问题描述】给定一个背包，它能够容纳一定重量的物品。
再给定一组物品，每个物品有自己的重量和价值。
要求在不超过背包容量的情况下，选择物品放入背包，使得背包中物品的总价值最大。
【算法及解决思路】⒈0 背包问题:⑴动态规划法：使用一个二维数组dpij表示前i个物品在背包容量为j时的最大总价值。
dpij的计算方法是在考虑第i个物品时，如果将其放入背包，则总价值为dpi-1j-wi + vi，如果不放入背包，则总价值为dpi-1j。
则dpij的值为这两种情况中的较大值。
⑵贪心算法：按物品的单位重量价值进行排序，然后依次选择单位重量价值最大的物品放入背包，直至放满或者无法再放入为止。
⒉0 背包问题的变体:⑴ 01背包问题：每个物品要么放入背包，要么不放入，无法进行分割。
⑵完全背包问题：每个物品可以无限次地放入背包，相当于01背包问题的物品数量为无穷。
⑶多重背包问题：每个物品有有限个数的可选择，相当于01背包问题的物品数量有限。
【算法复杂度】⒈0 背包问题：⑴动态规划法：时间复杂度为O(nW)，空间复杂度为O(nW)，其中n为物品数量，W为背包容量。
⑵贪心算法：时间复杂度为O(nlogn)，空间复杂度为O(1）⒉0 背包问题的变体：⑴ 01背包问题：时间复杂度同⒈0。
⑵完全背包问题：时间复杂度同⒈0。
⑶多重背包问题：时间复杂度同⒈0。
【附件】：本文档不涉及附件。
【法律名词及注释】：本文档不涉及法律名词及注释。
背包问题之零⼀背包注:参考⽂献《背包九讲》.零⼀背包问题⼀:题⽬描述 有 N 件物品和⼀个容量为 V 的背包.放⼊第 i 件物品耗⽤的费⽤为C i(即所占⽤背包的体积),得到的价值是 W i.求将哪些物品装⼊背包所得到的总价值最⼤.⼆:基本思路 01背包是最基础的背包问题,这道题的特点是每种物品仅有⼀件,可以选择放或不放,且不要求背包必须被放满,只要求最后的总价值最⼤. ⽤⼦问题定义状态:F[i][v] 表⽰对于前 i 件物品,当背包容量为 v 时所能得到的价值最⼤值.设想,将 "前 i 件物品放⼊容量为 v 的背包中" 这个⼦问题,若只考虑第 i 件物品的策略(要么放要么不放),那么就可以转化为⼀个之和前 i - 1 件物品相关的问题.如果不放第 i 件物品, 那么问题就转化为 ”前 i - 1 件物品放⼊容量为 v 的背包中“,价值就是 F[i - 1][v]; 如果放第 i 件物品,那么问题就转化为 ”前 i - 1 件物品放⼊剩下的容量为v - C i的背包中”, 此时获得的价值为 F[i - 1][v - C i] + W i。
特殊的，当 v < C i时，可以认为当前的容量是放不下第 i 件物品的，即此时相当于不放第 i 件物品的价值F[i - 1][v].分析到这⾥则可得状态转移⽅程为: F[i][v] = v < C i F[i - 1][v] : max( F[i - 1][v], F[i - 1][v - C i] + W i ).在这⾥要特别的说明⼀下,这个⽅程⾮常重要,⼀定要知道这是怎么推出来的,⼏乎后⾯的所有的背包问题都和这个⽅程有着密不可分的联系.伪代码如下:F[0...N][0...V] <--- 0for i <--- 1 to N for v <--- C i to V F[i][v] = v < C i F[i - 1][v] : max( F[i - 1][v], F[i - 1][v - C i] + W i );具体代码:1void _01Pack(int F[][MAXV], int N, int V, int C[], int W[]){2 memset(F, 0, sizeof(F));3for(int i = 1; i <= N; i++) {4for(int v = 0; v <= V; v++) {5 F[i][v] = v < C[i] ? F[i - 1][v] : max(F[i - 1][v], F[i - 1][v - C[i]] + W[i]); //放或者不放两者之中选择最优者6 }7 }8 }三:优化空间复杂度 可以清楚的看到上⾯算法的时间复杂度和空间复杂度均为 O(N * V), 这⾥时间复杂度已经不能得到优化,但是空间复杂度确可以优化到O(V). 先看上⾯代码是如何实现的.最外⾯⼀层循环,每次计算出⼆维数组 F[i][0...V] 的值,计算的时候 F[i][0...V] 是由它的上⼀层 F[i - 1][0...V] ⽽得到的.那么如果把这个数组换成⼀维的 F[v] 那么还能保留上⼀次的状态吗.答案是可以的.由于动态规划算法的⽆后效性,第 i + 1 件物品的选择与否不会影响到第 i 件物品(即它的前⼀件物品)的选择状态.那么可以在上⾯第⼆次循环中按照 v <--- V...0 递减的顺序来计算 F[v], 这样计算F[v] 时所需要的状态 F[v] 和 F[v - C i] + W i 仍然还是上⼀次的状态.⽽计算 F[v] 之后, v 的顺序是递减的, F[v] 不会影响到 F[v'] (v' < v), 因为F[v']只与 F[v'](上⼀次的值) 和 F[v - C i] 有关, ⽽ F[v] > F[v'] > F[v' - C i]. 所以⼜可得状态转移⽅程. F[v] = max( F[v], F[v - C i] + W i ).伪代码如下:F[0...V] <--- 0for i <--- 1 to N for v <--- V to C i F[v] = max( F[v], F[v - C i] + W i );具体代码:1void _01Pack(int F[], int N, int V, int C[], int W[]){2 memset(F, 0, sizeof(F));3for(int i = 1; i <= N; i++) {4for(int v = V; v >= C[i]; v--) {5 F[i][v] = max(F[v], F[v - C[i]] + W[i]);6 }7 }8 }可以看到从第⼀个状态转移⽅程到第⼆个状态转移⽅程的空间优化效率还是挺⼤的: F[i][v] = max( F[i - 1][v], F[i - 1][v - C i] + W i ). ----> F[v] = max( F[v], F[v - C i] + W i ).在第⼆个⽅程中 F[v]1 = max(F[v]2, F[v - C i] + W i), 其实 F[v]2 就相当与⽅程⼀中的 F[i - 1][v], 对应的 F[v - C i] + W i就相当于 F[i -1][v - C i] + W i.这⼀正确性是在内层循环递减的前提下才成⽴的.否则, 将内层循环改为递增, 那么 F[i][v] 其实是由 F[i][v] 和 F[i][v - C i] 推出来的,这不符合基本思路中的探讨.之前说过由于 01背包的特殊性,这⾥将 01背包抽象化,⽅便之后的调⽤.解决单个物品 01背包的伪代码:def ZeroOnePack (F, C, W) for v <--- V to C F[v] = max( F[v], F[v - C] + W );这么写之后, 01背包总问题解决的伪代码就可以改写成:F[0...V] <--- 0for i <--- 1 to N ZeroOnePack(F, C[i], W[i]);具体代码:1const int MAXN = 10000;2int N, V, C[MAXN], W[MAXN];34void ZeroOnePack(int F[], int C, int W) { // 对于单个物品的决策5for(int v = V; v >= C; v--) {6 F[v] = max(F[v], F[v- C] + W);7 }8 }910void solv(int F[]) {11 memset(F, 0, sizeof(F));12for(int i = 1; i <= V; i++) {13 ZeroOnePack(F, C[i], W[i]);14 }15 }四: 01背包问题的拓展 ------ 初始化的细节问题 在上述 01背包的问题中,仅问得是 “如何选取,才能使的最后的总价值最⼤”, 这⾥并没有规定是否必须装满背包, 但是有的题将会给予这个附加条件, 即“在要求恰好装满背包的前提下, 如何选取物品, 才能使的最后的总价值最⼤ ”. 这两种问法, 在代码实现上相差⽆⼏.如果是上述问法,要求 “恰好装满背包”, 那么在初始化时除了将 F[0] 赋值为 0 之外, 其他的 F[1...V] 都应该赋值为 -∞,这样就可以保证最后的得到的 F[V] 是⼀种恰好装满背包的最优解.如果没有要求必须把背包装满,⽽是只希望价值尽量最⼤,初始化时应该将F[0...V] 全部设置为 0. 之所以可以这么做,是因为初始化的 F[] 事实就是没有任何物品放⼊背包时的合法状态.如果要求背包恰好装满,那么只有容量为 0 的背包在什么也不装且价值为 0 的情况下被装 "恰好装满",其他容量的背包如果不装物品, 那么默认的情况下都是不合法状态,应该被赋值为 -∞, 即对于第⼀个物品⽽⾔, 其合法状态只能由 F[0] 转移得到.如果背包并⾮必须被装满,那么任何容量的背包在没有物品可装时都存在⼀个合法解,即什么都不装,且这个解的价值为 0.所以将其全部初始化为 0 是可以的. 注:这个技巧完全可以拓展到其他背包问题中.伪代码:def ZeroOnePack (F, C, W) for v <--- V to C F[v] = max( F[v], F[v - C] + W )end defdef slov() F[0] = 0, F[1...V] <--- -∞ for i <--- 1 to N ZeroOnePack(F, C[i], W[i])end def具体代码:1const int MAXN = 10000;2int N, V, C[MAXN], W[MAXN];34void ZeroOnePack(int F[], int C, int W) {5for(int v = V; v >= C; v--) {6 F[v] = max(F[v], F[v- C] + W);7 }8 }910void solv(int F[]) {11 F[0] = 0;12for(int i = 1; i <= V; i++) F[i] = INT_MIN; // 除F[0] = 0之外, 其他全部赋值为负⽆穷13for(int i = 1; i <= V; i++) {14 ZeroOnePack(F, C[i], W[i]);15 }16 }五:⼀个常数级别的优化上述伪代码的:for i <--- 1 to N for v <--- V to C i可以优化为:for i <--- 1 to N for v <--- V to max( V - SUM(i...N)C i, C i)。
01背包问题的数学逻辑01背包问题是一个经典的组合优化问题，在计算机科学和运筹学中具有重要的应用。
该问题可以描述为：给定一个背包，其承载重量有限，同时给定一系列物品，每个物品都有其对应的重量和价值，需要选择一些物品放入背包中，使得背包中物品的总重量不超过背包的承载重量，并且所选物品的总价值最大。
要解决01背包问题，可以使用动态规划的方法。
动态规划是一种通过将问题分解为子问题并以自底向上的方式解决的方法。
下面我们详细介绍01背包问题的解决过程。
我们定义一个二维数组dp，其中dp[i][j]表示当背包容量为j时，在前i个物品中选择物品的最大总价值。
其中i表示前i个物品，j表示背包的剩余容量。
接下来，我们根据动态规划的原则，可以得到状态转移方程：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])其中，w[i]表示第i个物品的重量，v[i]表示第i个物品的价值。
根据状态转移方程，我们可以看出，在选择第i个物品时，有两个选择：放入背包中或不放入背包中。
如果选择放入背包中，则剩余的背包容量为j-w[i]，此时的总价值为dp[i-1][j-w[i]] + v[i]。
如果选择不放入背包中，则总价值为dp[i-1][j]，取两者的最大值作为dp[i][j]的值。
为了得到dp数组中的所有值，我们需要按照自底向上的方式依次计算每个dp[i][j]。
最终，dp[n][m]即为问题的最优解，其中n表示物品的个数，m表示背包的承载重量。
具体的解决过程如下：1.初始化dp数组，将所有元素置为0。
2.从i=1到n，依次遍历每个物品。
a.对于每个物品i，从j=0到m，依次遍历每个背包容量。
b.如果w[i] > j，表示当前背包容量无法容纳物品i，则dp[i][j] = dp[i-1][j]。
c.如果w[i] <= j，表示当前背包容量可以容纳物品i，则-如果选择放入物品i，总价值为dp[i-1][j-w[i]] + v[i]。
背包问题报告小组成员：张灿、吴雪涛、高坤、占强、习慧平小组分工情况小组成员查找资料制作ppt 编写程序讲解ppt 制作报告张灿ⅴⅴⅴⅴⅴ吴雪涛ⅴ高坤ⅴⅴ占强ⅴ习慧平ⅴ背包问题一、背包问题的历史由来它是在1978年由Merkel和Hellman提出的。
它的主要思路是假定某人拥有大量物品，重量各不同。
此人通过秘密地选择一部分物品并将它们放到背包中来加密消息。
背包中的物品中重量是公开的，所有可能的物品也是公开的，但背包中的物品是保密的。
附加一定的限制条件，给出重量，而要列出可能的物品，在计算上是不可实现的。
背包问题是熟知的不可计算问题，背包体制以其加密，解密速度快而其人注目。
在解决大量的复杂组合优化问题时，它常常作为一个子问题出现，从实际的观点看，许多问题可以用背包问题来描述，如装箱问题，货仓装载，预算控制，存储分配，项目选择决策等，都是典型的应用例子。
随着网络技术的不断发展，背包公钥密码在电子商务中的公钥设计中也起着重要的作用。
然而当问题的规模较大时，得到最优解是极其困难的。
但是，大多数一次背包体制均被破译了，因此现在很少有人使用它。
二、背包问题的描述背包问题(Knapsack problem)是一种组合优化的NP完全问题。
问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。
问题的名称来源于如何选择最合适的物品放置于给定背包中。
相似问题经常出现在商业、组合数学，计算复杂性理论、密码学和应用数学等领域中。
也可以将背包问题描述为决定性问题，即在总重量不超过W的前提下，总价值是否能达到V？三、背包问题的定义我们有n种物品，物品j的重量为w j，价格为p j。
我们假定所有物品的重量和价格都是非负的。
背包所能承受的最大重量为W。
如果限定每种物品只能选择0个或1个，则问题称为0-1背包问题。
可以用公式表示为：maximizesubject to如果限定物品j最多只能选择b j个，则问题称为有界背包问题。
可以用公式表示为：maximizesubject to如果不限定每种物品的数量，则问题称为无界背包问题。
四、背包问题的研究现状Dantzing在20 世纪50 年代首先进行了开创性的研究，利用贪婪算法求得了0-1背包问题最优解的上界。
1974 年，horowitz 和salmi利用分支限界法解答背包问题，并提出了背包问题的可分性，指出了求解该问题的一条新途径。
随后，balas 和zemel 提出了背包问题的“核”思想，使背包问题的研究获得了较大进展。
上世纪九十年代以后，随着生物仿生技术和网络技术的飞速发展，各种模拟生物物理规律的并行近似算法不断涌现，例如遗传算法己经在0/1背包问题上得到较好的应用，蚂蚁算法、粒子群算法等仿生算法也在组合优化问题中得到了很好的应用。
五、求解0-1背包问题常见方法传统求解该问题的方法可以概括为精确算法和近似算法，其中精确算法有动态规划法、回溯法、分支限界法等，近似算法有遗传算法、贪婪法、粒子群算法、蚁群算法等,由于精确算法的时间复杂性和空间复杂性等缺点，近年来利用近似算法求解背包问题成为重点。
5.1精确算法5.1.1回溯法回溯法的基本思想是在包含问题的所有解的解空间树中,按照深度优先的策略,从根结点出发搜索解空间树，其用来求问题的所有解时,要回溯到根,且根结点的所有子树都已被搜索遍才结束。
用回溯法求解0-1 背包问题是按照物品的单位价值从大到小排序,计算当前节点的上界,搜索左子树。
只有当右子树包含可行解时才搜索右子树。
剪去右子树的条件是当前价值加上剩余物品的总价值小于当前的最优总价值时,不需搜索右子树,可将右子树剪去。
回溯法用一定的剪枝进行优化,算法的时间复杂度为o(n2n), n为物品个数。
5.1.2动态规划法动态规划法是上世纪50年代Richard Bellman创建的解决多阶段决策过程最优化的一种数学方法，即把多阶段决策问题变换为一系列相互联系单阶段问题，然后逐个加以解决。
它的特点是解决多阶段、离散性问题。
动态规划算法的基本思想是把原问题分解成一系列子问题,然后从这些子问题中求出原问题的解。
对一个负重能力为 C 的背包,如果选择装入第i 种物品,那么原背包问题就转化为负重能力为C-ci的子背包问题。
动态规划算法是一种经典的背包问题求解算法，其原理简单，算法思路清晰，易于实现。
动态规划算法虽然高效，但是对于规模较大的问题它不是一个理想的算法，主要原因就是它的维数障碍，即计算和存储量的需要对于状态空间和决策空间的维数的增长呈指数增长关系。
动态规划算法的时间复杂度为o(min(n·C，2^n)),其中n 为物体的个数,C为背包负重。
精确算法的优点是当问题规模较小时一定可以求得最优解，缺点是当问题规模较大时因计算量太大而无法实现。
所以一些学者提出了各种近似算法来解决精确算法求解背包问题时的时间复杂性和空间复杂性难题。
5.2近似算法5.2.1贪婪算法贪婪算法是一种逐步构造最优解的启发式算法，其基本思想是在每一阶段它都在一定的规则下构造出当前看似最优的一个决策，决策一旦做出就不再更改。
贪婪算法常以当前情况为基础作最优选择，而不考虑整体情况，所以贪婪法一般可以快速得到满意的解，因为它省去了为找最优解要穷尽所有可能而必须耗费的大量时间。
虽然这种启发式的策略并不一定能够获得最优解,然而在许多情况下确能达到预期的目的。
贪婪算法解决优化问题的最关键问题是制定贪婪策略。
对于背包问题来说，贪婪的策略有常用的3种。
它们是价值贪婪准则、质量贪婪准则和价值密度贪婪准则。
每种贪婪策略都采用多步过程来完成背包的装入。
在每一步过程中利用贪婪准则选择一个物品装入背包。
其中采用价值密度(价值重量比pi/ci)的贪婪准则是从剩余物品中选择可以放入背包的pi/ci值最大的物品，直到超出背包容量限制装不下为止，并将未装入背包的物品编码修正为0。
算法的时间复杂度为o(nlogn)。
这种策略对于连续背包问题可保证得到最优解，但对于0／1背包问题不一定能得到最优解。
因此出现了一些对于贪婪算法的改进方法，例如文献中提出的算法在不增加时间复杂度的基础上，保证求解质量较稳定地优于价值密度贪婪算法及价值密度改进算法。
近年来还产生了贪婪法与其他算法结合的混合算法，有赵新超，杨婷婷提出的更贪心粒子群算法, 该算法对超过背包重量限制的粒子的处理方法是去掉已经装进去且性价比最差的物品，直到满足重量约束条件为止，这样在改善粒子质量的同时避免了罚函数方法中敏感的参数选择问题；对于可行粒子的处理措施是将还未装入背包且性价比最好的物品装进背包，直到不能装为止。
结果表明更贪心粒子群算法无论在寻优能力、计算速度和稳定性方面都有很好的表现，非常适合于求解大规模背包问题。
还有刘茜、马杰良提出的混合遗传算法，它针对遗传操作交叉和变异的过程中不符合约束条件的个体，在解码过程中引入贪婪算法优先装入价值重量比大且物品标记为1 的物品，直至背包容量限制装不下为止，通过引进贪婪算法使得遗传进化过程以良好的种子为基础进行，此外算法在变异操作和进化终止条件的设计上也进行了改进，结果表明该算法在解的质量和求解速度方面都比遗传算法有很大的改良。
5.2.2蚁群算法蚁群算法是由意大利学者Dorigo M.等提出的一类模拟蚂蚁群体觅食行为的仿生优化算法。
算法的基本思想是蚂蚁将根据信息素的多少选择走哪一条路，蚂蚁在觅食过程中会留下一种称为信息素的物质，若蚂蚁从巢穴到食物源所走的路径较短，则该蚂蚁从巢穴到食物源后再返回巢穴的时间也就较短，这样同时间内在较短路径上蚂蚁分泌的信息素就会较多。
后面的蚂蚁将根据其他蚂蚁留下来信息素的多少而选择路径，某一条路径上的信息素越多，则这条路径被选择的概率越大。
蚂蚁群体的这种集体行为构成了一种学习信息的正反馈机制，蚂蚁之间通过信息素来交流信息。
蚁群算法模拟了这种优化机制，通过个体之间的信息交流与协作来寻找最优解。
蚁群算法现已成功运用在TSP、图像处理、车辆路径系统、通信系统等领域。
它具有较强的鲁棒性、分布性、全局优化性和易与其它优化算法融合的优点,现已是解决NP-hard问题的一个有效工具。
蚁群算法解决0/1 背包问题的核心是：在某一物品上聚集的信息素越多，则该物品被选择的概率就越大。
背包问题的蚁群算法求解过程是：①设置迭代次数；②将各蚂蚁置于相应变量的0、1位置点；按转移概率移动各蚂蚁；按强度更新方程更新信息素轨迹；记录当前最佳蚂蚁位置；③返回步骤②循环直到满足退出条件。
就蚁群算法而言当处理的数据比较小时其具有很快的收敛速度，而随着数据规模的增大算法的收敛速度明显降低。
蚁群算法在减少寻优计算量和缩短算法运行时间方面，有待进一步改进。
针对蚁群算法的缺点，许多学者对蚁群算法进行了改进。
赵朝卿，胡小兵等提出了一种求解0-1背包问题的混合型算法(KPAICACA)，先利用蚁群算法求优化解，然后利用抗体克隆选择算法扩大解的搜索空间，使得在收敛速度和寻优能力两方面都有明显改善。
具体方法是：每个物品i的属性有重量ci，价值pi和信息素τi，即信息素积累在物品上。
选择物品i的期望度为ηi=pi/ci。
每只蚂蚁都附一个背包和一个禁忌表，蚂蚁将根据选中物品的重量来决定是否将其装入背包。
若物品装入背包而不超过其容量，则继续选择下一个物品；否则将其编号放入禁忌表中，以后选择物品时不再考虑。
经过n 次选择，构建了一个由物品编号表示的解，当m 只蚂蚁都构建了自己的解，将这些编号解变换为0-1 序列解，每个序列解被视做一个抗体，抗体编码的长度为n，抗体群的规模等于蚂蚁种群的规模m。
随后对抗体群进行克隆、变异和选择操作。
抗体免疫克隆算法搜索完成后，根据背包中物品的价值总和P，记录最优解以及对应的物品价值总和，并对物品上的信息素进行更新。
5.2.3遗传算法遗传算法己被广泛地应用组合优化领域,其全局最优性、可并行性、高效性在函数优化中得到了广泛地应用。
遗传算法是将问题的每一个可能性解看作是群体中的一个个体(染色体),并将每一个染色体编码成串的形式,再根据预定的目标函数对每个个体进行评价,给出一个适应值。
算法将根据适应度值进行它的寻优过程,遗传算法的寻优过程是通过选择、杂交和变异等遗传算子来具体实现的。
它的搜索能力由选择算子和杂交算子决定,变异算子则保证了算法能够搜索到问题空间的每一个点,从而使其具有搜索全局最优的能力。
遗传算法的时间复杂度为O(T* n^2),其中T为迭代次数，n为种群个数。
运用简单的遗传算法（SGA，Simple Genetic Algorithm）求解背包问题时若问题规模不大也能够得到最优解或近似最优解，但当规模较大时，算法容易早熟，得不到比较理想的结果，所以需要对其进行改进。
