《算法分析与程序设计动态规划及回溯法解01背包问题》由会员分享，可在线阅读，更多相关《算法分析与程序设计动态规划及回溯法解01背包问题（19页珍藏版）》请在金锄头文库上搜索。
1、动态规划法、回溯法解 0-1 背包问题2012 级 计科 庞佳奇一、 问题描述与分析1. 动态规划算法通常用于求解具有某种最优性质的问题。 在这类问题中， 可能会 有许多可行解。 每一个解都对应于一个值， 我们希望找到具有最优值的解。 动态规 划算法与分治法类似， 其基本思想也是将待求解问题分解成若干个子问题， 先求解 子问题， 然后从这些子问题的解得到原问题的解。 与分治法不同的是， 适合于用动 态规划求解的问题， 经分解得到子问题往往不是互相独立的。 若用分治法来解这类 问题， 则分解得到的子问题数目太多， 有些子问题被重复计算了很多次。 如果我们 能够保存已解决的子问题的答案， 而在需要
2、时再找出已求得的答案， 这样就可以避 免大量的重复计算， 节省时间。我们可以用一个表来记录所有已解的子问题的答案。 不管该子问题以后是否被用到， 只要它被计算过， 就将其结果填入表中。 这就是动 态规划法的基本思路。 具体的动态规划算法多种多样， 但它们具有相同的填表格式。多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策 依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产 生出来的，故有“动态”的含义，称这种解决多阶段决策最优化问题的方法为动 态规划方法。任何思想方法都有一定的局限性，超出了特定条件，它就失去了作 用。同样，动态规划也并不是万能的。适用动态
3、规划的问题必须满足最优化原理 和无后效性。 1. 最优化原理（最优子结构性质） 最优化原理可这样阐述：一个最 优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。2.无后效性将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段 的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。这就是无后向性，又称为无后效性。3子问题的重叠性动态规划将原来具有指数级时间复杂度的搜索算法改进成了具
4、有 多项式时间复杂度的算法。其中的关键在于解决冗余，这是动态规划算法的根本 目的。动态规划实质上是一种以空间换时间的技术，它在实现的过程中，不得不 存储产生过程中的各种状态，所以它的空间复杂度要大于其它的算法。01背包是在M件物品取出若干件放在空间为W的背包里，每件物品的体积为W1 , W2Wn，与之相对应的价值为 P1,P2Pn。求出获得最大价值的2.回溯法（探索与回溯法）是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。在包含问题的所有解的
5、解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。（其实回溯法就是对隐式图的深度优先搜索算法）。若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束可用回溯法求解的问题 P,通常要能表达为：对于已知的由 n元组（x1 , x2 ,， xn ）组成的一个状态空间 E= （x1 , x2 ,，xn ） I xi Si , i=1 , 2,，n，给定 关
6、于n元组中的一个分量的一个约束集 D，要求E中满足D的全部约束条件的所有 n 元组。其中Si是分量xi的定义域，且|Si|有限，i=1 , 2,，n。我们称E中满足D 的全部约束条件的任一 n元组为问题P的一个解。解问题P的最朴素的方法就是枚举法，即对E中的所有n元组逐一地检测其是否满足D的全部约束，若满足，则为问题 P的一个解。但显然，其计算量是相当大的。我们发现，对于许多问题，所给定的约束集D具有完备性，即i元组（xi , x2，xi） 满足D中仅涉及到xi , x2 ,，xi的所有约束意味着j （j=i ）元组（xi , x2 ,，xj） 定也满足 D中仅涉及到xi , x2 ,，xj的
7、所有约束，i=1 , 2 ,，n。换句话 说，只要存在0 j i j。因此，对于约束 集D具有完备性的问题P, 旦检测断定某个j元组（xi , x2 ,，xj）违反D中仅 涉及xi , x2 ,，xj的一个约束，就可以肯定，以（ xi , x2，xj）为前缀的任何n元组（xi , x2 ,，xj, xj+i ,，xn）都不会是问题 P的解，因而就不必去搜索 它们、检测它们。回溯法正是针对这类问题， 利用这类问题的上述性质而提出来的比枚 举法效率更高的算法。二、 算法设计（或算法步骤）i. 这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。用子问题定义状态：即fiv表示前i件物品
8、恰放入一个容量为v的背包可以获得的最大价-可编辑修改-值。则其状态转移方程便是：fiv=maxfi-1v,fi-1v-ci+wi这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它 详细解释一下： “将前 i 件物品放入容量为 v 的背包中”这个子问题，若只考虑第 i 件物 品的策略(放或不放)，那么就可以转化为一个只牵扯前 i-1 件物品的问题。如果不放 第 i 件物品，那么问题就转化为 “前 i-1 件物品放入容量为 v 的背包中” ，价值为 fi-1v ； 如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-ci的背包中”，此时能获得的最
9、大价值就是fi-1v-ci再加上通过放入第i件物品获得的价值 wi。2. (1 ) 分析要解决的问题，给出你的思路，可以借助图表等辅助表达。01 背包问题用回溯法实现就是要枚举其所有的解空间，时间复杂度为(2)nO 左右。 搜索的具体方法如下：对于每一个物品i，对于该物品只有选与不选2个决策，总共有n个物品，可以顺序依次考虑每个物品，这样就形成了一棵解空间树：基本思想就是遍历这棵树，以枚举所有情况，最后进行判断，如果重量不超过背包 容量，且价值最大的话，该方案就是最后的答案。利用回溯算法写还可以加入一些优化，进行剪枝，因为很多情况是没有意义的，例如当 重量大于背包容量的时候，没有必要对剩下的物
10、品再来决策了。或者将剩下的所有物品 都选取其总价值也没有目前已经求得的方案的价值还大的话，也是可以剪枝的。(2 )分析利用你的想法解决该问题可能会有怎样的时空复杂度。时间复杂度估计：(2)nO 因为物品只有选与不选 2 个决策，而总共有 n 个物品，所以时间复杂度为(2)nO 。 空间复杂度估计： ()On 因为递归栈最多达到 n 层，而且存储所有物品的信 息也只需要常数个一维数组，所以最终的空间复杂度为 ()On 。算法实现1. 动态规划#include#includeint c5050;int w10,v10;int x10;int n;void KNAPSACK_DP(int n,int
11、 W);void OUTPUT_SACK(int c5050,int k) ;void KNAPSACK_DP(int n,int W)int i,k;for(k=0;k=W;k+)c0k=0;for(i=1;i=n;i+)ci0=0;for(k=1;k=W;k+)if(wici-1k)cik=vi+ci-1k-wi;elsecik=ci-1k;elsecik=ci-1k;void OUTPUT_SACK(int c5050,int k)int i;for(i=n;i=2;i-)if(cik=ci-1k)xi=0;elsexi=1;k=k-wi;x1=(c1k?1:0);for(i=1;i=n
12、;i+)printf(%4d,xi);void main()int m;int i,j,k;printf( 输入物品个数 :);scanf(%d,&n);printf( 依次输入物品的重量 :n);for(i=1;i=n;i+)scanf(%d,&wi);printf( 依次输入物品的价值 :n);for(i=1;i=n;i+)scanf(%d,&vi);printf( 输入背包最大容量 :n);scanf(%d,&m);for(i=1;i=m;i+)printf(%4d,i);-可编辑修改 -prin tf(n);KNAPSACK_DP( n, m);printf(构造最优解过程如下:n);
13、for(j=1;jv=5;j+)for(k=1;k=m;k+)prin tf(%4d,cjk);prin tf(n);printf(最优解为:n);OUTPUT_SACK(c,m); system(pause);-可编辑修改-可编辑修改-D 九 CDe bu gOL，亡祇-盼鞍隣*重量 依哀議鵬品反价值 钦龍典容量_21234构造最优过程如花11111最优解为：1 1111111i请按任意键继续.-可编辑修改-2. 回溯法#include #include #include typedef struct goodsdouble *value; / 价值double *weight; / 重量char *select; / 是否选中到方案int num;/ 物品数量double limitw; / 限制重量GOODS;double maxvalue,totalvalue;char *select1;void backpack(GOODS *g, int i, double tw, double tv) int k;if (tw + g-weighti limitw)select1i = 1;if
