《枚举回溯动态规划解决01背包问题课程设计论文》由会员分享，可在线阅读，更多相关《枚举回溯动态规划解决01背包问题课程设计论文（12页珍藏版）》请在金锄头文库上搜索。
1、 一、 问题描述01背包问题： 一个商人带着一个能装m千克的背包去收购货物。现有n种货物，且第i种货物有wi千克，可获得pi元。假设货物不能拆零，请编写算法帮助商人收购货物，获得最高利润。二、 算法设计与分析枚举法分析： 设n个物品的重量和价值分别存储于数组w 和v 中，限制重量为tw.考虑一个n元组（x0，x1，xn-1），其中xi=0 表示第i个物品没有选取，而xi=1则表示第i个物品被选取。用枚举法解决背包问题，需要枚举所有的选取方案，而根据上述方法，我们只要枚举所有的n元组，就可以得到问题的解。 显然，每个分量取值为0或1的n元组的个数共为2n个。而每个n元组其实对应了一个长度为n的二
2、进制数，且这些二进制数的取值范围为02n-1.因此，如果把02n-1分别转化为相应的二进制数，则可以得到我们所需要的2n个n元组。 回溯法分析： 先确定搜索空间：n件物品的取舍数字化，”取”标识为1，否则为0，则搜索的空间为一维数组如：（0,0,0、0,0），（0,0,0、0，1），（0,0,0、10）、（1,1,1、1，1）这是一颗子集树确定约束条件：所取物品的质量和不超过m，只有取当前物品时才需要判断所取的质量和不超过m，若不取当前物品时，就无需进行判断，只要一步步进行搜索。搜索过程中的主要操作：累加所取物品的质量，回溯是还要做现场清理，也就是将当前的物品置为不取状态，且从累加质量中减去当
3、前物品的质量。动态规划法：0-1背包问题可以看作是寻找一个序列，对任一个变量 的判断是决定=1还是之后，已经确定了，在判断时，会有两种情况：（1） 背包容量不足以装入物品i，则=0，背包的价值不增加；（2） 背包的容量可以装下物品i，则=1，背包的价值增加。这两种情况下背包的总价值的最大者应该是对判断后的价值。 我们可以一步一步的解出我们所需要的解。第一步，只装入第一个物品，确定在各种情况下背包能得到的最大价值；第二步，只装入前两个物品，确定在各种情况下的背包能够得到的最大价值；一次类推，到了第n步就得到我们所需要的最优解了。三、 测试分析1） 枚举法对于一个有n个元素的集合，其子集数量为，所
4、以，不论生成子集的算法效率有多高，穷举法都会导致一个的算法。2） 回溯法由于计算上界的函数需要O(n)时间，在最坏情况下有个右儿子结点需要计算上界，所以解0-1背包问题的回溯法算法所需要的计算时间为3） 动态规划由于函数中有一个两重for循环，所以时间复杂度为O(n+1)x(m+1).空间复杂度也是O(n+1)x(m+1)，即O（nm）.四、 附录：源代码1） 枚举法#include using namespace std;#include #define MAX 100 #include #include/将n化为二进制形式，结果存放到数组b中void conversion(int n,in
5、t bMAX) int i; for(i=0;iMAX;i+) bi = n%2; n = n/2; if(n=0)break; void main()long start,end;start=clock();int i,j,n,bMAX,tempMAX; float tw,maxv,wMAX,vMAX,temp_w,temp_v; coutn; / 输入物品个数 couttw; / 输入背包的限制重量 /输入各个物品的重量 coutplease input the weight : ; for(i=0;iwi; /输入各个物品的价值 coutplease input the value :
6、; for(i=0;ivi; maxv = 0;/*穷举2n个可能的选择，找出物品的最佳选择*/ for (i=0;ipow(2,n);i+) for (j=0;jn;j+) bj = 0; conversion(i,b); temp_v = 0; temp_w = 0; for (j=0;jn;j+) if (bj=1) temp_w = temp_w+wj; temp_v = temp_v + vj; /*试探当前选择是否是最优选择，如果是就保存下来*/ if (temp_w maxv) for (j=0;jn;j+) tempj = 0; maxv = temp_v; for (j=0;
7、jn;j+) tempj = bj; coutthe max values : maxvendl; / 输出放入背包的物品的最大价值coutthe selection is:;/*输出物品的选择方式*/ for (j=0;jn;j+) couttempj ; coutendl; end=clock(); cout运行时间为：end-start毫秒endl;2） 回溯法#include#includeint tw; /背包容量 int n; /物品数 int w100; /存放n个物品重量的数组 int v100; /存放n个物品价值的数组 int currentWeight=0; /当前重量
8、int currentPrice=0; /当前价值 int bestPrice=0; /当前最优值 int bestAnswer100; /当前最优解 int bp=0;int bA100; /当前最优解 int times=0;void Print(); void Backtracking(int i) times+=1;if(in) Print();if(bestPricebp)bp=bestPrice;for(int j=1;j=n;j+) bAj=bestAnswerj;return; if(currentWeight+wi=tw) /将物品i放入背包，搜索左子树 bestAnswer
9、i = 1; currentWeight += wi; bestPrice +=vi; Backtracking(i+1); /完成上面的递归，返回到上一结点，物品i不放入背包，准备递归右子树 currentWeight -= wi; bestPrice -= vi; bestAnsweri = 0; Backtracking(i+1); void Print() int i; printf(n路径为 ); for(i=1;in;+i) printf(%d,bestAnsweri); printf(%dt价值为%dn,bestAnsweri,bestPrice); void main() lo
10、ng start,end;start=clock();int i; /*输入部分*/ printf(please input n:n); scanf(%d,&n); printf(please input tw:n); scanf(%d,&tw); printf(please input w:n,n); for(i=1;i=n;i+) scanf(%d,&wi); printf(please input v:n,n); for(i=1;i=n;i+) scanf(%d,&vi);printf(各符合条件的路径为：n); Backtracking(1);printf(nthe best answ
11、er is ); for(i=1;in;+i) printf(%d,bAi); printf(%dtthe price is %dn,bAi,bp); printf(nn总共搜索结点数%dn,times); end=clock();printf(运行时间为%d毫秒n,end-start); 3） 动态规划#include#include#define max(a,b) ab?a:b#define M 100void display(int &n,int &C,int sM,int pM) int i; coutn; coutendl; coutC; coutendl; coutplease input w:endl; s0=0; for(i=1;isi; coutplease input vendl; p0=0; for(i=1;i=n;i+)
