实验报告8 蛮力动态规划01背包.doc

《算法设计与分析》实验报告八 学 号： 1004091130 姓 名： 金玉琦 日 期： 2011-12-5 得 分： 一、实验内容： 分别用蛮力法、动态规划法、回溯法和分支限界法求解0/1背包问题。 二、所用算法的基本思想及复杂度分析： 蛮力法 基本思想 用蛮力法求解就是要穷举出物品的所有组合，计算不超过背包容量的物品的最大价值和 复杂度分析 装法有2n种组合，每种组合中又要计算价值和，所以其复杂度为指数级。 动态规划法 基本思想 动态规划法的关键在于找到决策函数，在本例中，令V(i,j)表示在前i个物品中能够装入容量为j的背包中的物品的最大值,则有如下动态规划函数： V(i,0)=V(0,j)=0; (1) V(i-1,j) jwi V(i,j)= (2) max{V(i-1,j),V(i-1,j-wi)+vi} j=wi 式(1)表明：把前面i个物品的装入容量为0的背包和把0个物品装入容量为j的背包，得到的总价值都是0。式(2)的第一个式子表明：如果第i个物品的重量大于背包的容量，则装入前i个物品得到的最大值和装入前i-1个物品得到的最大价值是相同的，即物品i不能装入背包；第二个式子表明：如果第i个物品的重量小于背包的容量，则会有以下两种情况：1.如果把第i个物品装入背包，则背包中的物品价值等于把前i-1个物品装入容量为j-wi的背包中的价值加上第i个物品的价值vi；2.如果第i个物品没有装入背包，则背包中物品的价值就等于把前i-1个物品装入容量为j的背包中所取得的价值。显然取二者的较大值作为把前i个物品装入容量为j的背包中的最优解。 复杂度分析 时间复杂度是O(n*c)。 回溯法 基本思想 回溯法是一种有组织的系统化有哪些信誉好的足球投注网站技术，可以看作是蛮力法穷举有哪些信誉好的足球投注网站的一种改进。具体在0/1背包问题中的使用如下： 回溯法从0/1背包问题的解空间树的根节点出发，按照深度优先遍历解空间树，有哪些信誉好的足球投注网站满足约束条件的解。在有哪些信誉好的足球投注网站到树中的任一结点时，先判断该结点的对应部分的解是否满足约束条件，或者是否超出目标函数的界,也就是判断该结点是否包含问题的(最优)解，如果不包含则跳过对以该结点为根的子树的有哪些信誉好的足球投注网站；否则进入以该结点为根的子树继续深度优先遍历有哪些信誉好的足球投注网站。 复杂度分析 0/1背包问题的解空间树是一棵子集树，遍历一棵子集树所需时间为Ω(2n)。 分支限界法 基本思想 分支限界法按照广度优先法遍历整个解空间树，在遍历过程中，对已经处理过的每一个结点根据限界函数估算目标函数的可能值，从中选取使目标函数取得极大或极小的结点优先进行广度优先有哪些信誉好的足球投注网站，从而不断调整有哪些信誉好的足球投注网站方向，尽快找到问题的最优解。 复杂度分析 由于分治限界法是蛮力法的一种改进，所以在0/1背包问题中，问题的复杂度在最坏的情况下是指数阶的。 三、源程序及注释： #define MAX 100 #define max(a,b) (ab)?a:b #include MATH.H #include VECTOR #include stdio.h #include stdlib.h #include WINDOWS.H #include TIME.H #include IOSTREAM #include algorithm using namespace std; //设计物品属性，重量和价值 typedef struct{ double w; //重量 double v; //价值 }OBJECT; //回溯法 int bestV=0; //最大价值 int cw=0; //当前重量 int cv=0; //当前价值 //进入右子树条件 int R_Bentch(int i,int n,int c,OBJECT t[]) { int j=i; int left_C=c-cw; int tempV=cv; while(t[j].wleft_Cjn) { left_C-=t[j].w; tempV+=t[j].v; j++; } return tempV; } //递归 void BackTrack(int i,int n,int c,OBJECT t[]) { if (i=n) { if(bestVcv) bestV=cv; return; } if(cw+t[i].w=c) //进入左子树 { cw+=t[i].w; cv+=t[i].v; BackTrack(i+1,n,c,t); cw-=t[i].w;