01背包問题的回溯法求解实验报告.doc

一、实验目的 实验内容? 问题描述 给定n种物品和一背包。物品i的重量是wi0，其价值为vi0，背包的容量为c。问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大？ ? 编程任务 利用回溯法试设计一个算法求出0-1背包问题的解，也就是求出一个解向量ｘi (ｘi = 0 或１，ｘi = 0表示物体ｉ不放入背包，ｘi ＝1表示把物体ｉ放入背包）， 使得尽量多的价值装入背包。 ? 数据输入 由文件input.txt提供输入数据n，c，及每个物品的重量w[ ]和价值v[ ]。 ? 结果输出 程序运行结束时，将最优解输出到文件output.txt中。 输入文件示例 输出文件示例 input.txt output.txt 4 5 2 1 3 2 12 10 20 15 1 1 0 1 三、实验环境 01背包问题用回溯法实现就是要枚举其所有的解空间，时间复杂度为左右。 有哪些信誉好的足球投注网站的具体方法如下： 对于每一个物品i，对于该物品只有选与不选2个决策，总共有n个物品，可以顺序依次考虑每个物品，这样就形成了一棵解空间树： 基本思想就是遍历这棵树，以枚举所有情况，最后进行判断，如果重量不超过背包容量，且价值最大的话，该方案就是最后的答案。 利用回溯算法写还可以加入一些优化，进行剪枝，因为很多情况是没有意义的，例如当重量大于背包容量的时候，没有必要对剩下的物品再来决策了。或者将剩下的所有物品都选取其总价值也没有目前已经求得的方案的价值还大的话，也是可以剪枝的。 分析利用你的想法解决该问题可能会有怎样的时空复杂度。 时间复杂度估计： 因为物品只有选与不选2个决策，而总共有n个物品，所以时间复杂度为。 空间复杂度估计： 因为递归栈最多达到n层，而且存储所有物品的信息也只需要常数个一维数组，所以最终的空间复杂度为。 五、 根据上面的分析，有哪些信誉好的足球投注网站的具体方法如下： 对于每一个物品i，对于该物品只有选与不选2个决策，总共有n个物品，可以顺序依次考虑每个物品，这样就形成了一棵解空间树，由父亲节点往下有哪些信誉好的足球投注网站的时候，往左表示选择该物品，并且将该物品的重量和价值追加到总重量和总价值中，最后，当到达第n+1层的时候，表示所有的物品都已经决策完了，可以比较和更新最优值。 当所有的分支和节点都遍历完时，此时的最优值就是原问题的最优值。 优化方法： 剪枝一：可以进行剪枝，因为很多情况是没有意义的，当重量大于背包容量的时候，没有必要对剩下的物品再来决策了。 剪枝二：将剩下的所有物品都选取其总价值也没有目前已经求得的方案的价值还大的话，也可以返回。 描述你在进行实现时，主要的函数或操作内部的主要算法；分析这个算法的时、空复杂度，并说明你设计的巧妙之处，如有创新，将其清晰的表述。 void Knapsack(Typep p[ ], Typew w[ ], Typew c, int n) { //为Knap::Backtrack 初始化 Typew W = 0; Typep P = 0; FILE *fp; Object * Q = new Object[n]; for ( int i = 1; i = n; i++ ) { Q[ i-1]. ID = i; Q[ i-1]. d =1.0*p[i]/w[i]; P += p[i]; W += w[i]; } Sort( Q, n);//对背包里的物品按性价比排序 Knap Typew, Typep K; K.p = new Typep[ n+1 ]; K.w = new Typew[ n+1 ]; K.x = new int[ n+1 ]; for (i = 1; i = n; i++){ K.p[i] = p[ Q[i-1].ID]; K.w[i] = w[ Q[i-1].ID]; } K.cp = 0; K. cw = 0; K.c = c; K.n = n; K.bestp = 0; // 回溯有哪些信誉好的足球投注网站 K.Backtrack(1); delete [ ] Q; delete [ ] K.w; delete [ ] K.p; if ((fp=fopen(output.txt,w))==NULL) { fprintf(stderr, Cannot open input file.\n); exit(0); } fprintf(fp,%d,%d,%d,%d,K.x[4],K.x[1],K.x[2],K.x[3]); fclose(fp); cout当前最优装配:; coutK.x[4]; for (i=1;in;i