实验报告 回溯法01背包.doc

算法设计与分析实验报告六学号： 1004091130 姓名： 金玉琦 日期： 2011-11-17 得分： 一、实验内容： 运用回溯法解决0-1背包问题 二、所用算法的基本思想及复杂度分析：回溯法回溯法就是一种有组织的系统化搜索技术, 可以看作是蛮力法穷举搜索的改进。回溯法每次只构造可能解的一部分, 然后评估这个部分解, 如果这个部分解有可能导致一个完整解, 则对其进一步构造, 否则, 就不必继续构造这个部分解了。回溯法常常可以避免搜索所有的可能解。0-1背包问题 1）基本思想给定n 种物品和一个容量为C 的背包, 物品i 的重量是Wi, 其价值为Vi , 0/ 1 背包问题是如何选择装入背包的物品(物品不可分割) , 使得装入背包中物品的总价值最大，设计可能解的表示方式, 构成解空间树。2）复杂度分析时间复杂度是O(2n);三、源程序及注释：#include using namespace std; class Knap friend int Knapsack(int p,int w,int c,int n ); public: void print() for(int m=1;m=n;m+) coutbestxm ; coutendl; ; private: int Bound(int i); void Backtrack(int i); int c;/背包容量 int n; /物品数 int *w;/物品重量数组 int *p;/物品价值数组 int cw;/当前重量 int cp;/当前价值 int bestp;/当前最优值 int *bestx;/当前最优解 int *x;/当前解 ; int Knap:Bound(int i) /计算上界 int cleft=c-cw;/剩余容量 int b=cp; /以物品单位重量价值递减序装入物品 while(i=n&wi=cleft) cleft-=wi; b+=pi; i+; /装满背包 if(in) if(bestpcp) for(int j=1;j=n;j+) bestxj=xj; bestp=cp; return; if(cw+wibestp)/搜索右子树 xi=0; Backtrack(i+1); class Object friend int Knapsack(int p,int w,int c,int n); public: int operator=a.d); private: int ID; float d; ; int Knapsack(int p,int w,int c,int n) /为Knap:Backtrack初始化 int W=0; int P=0; int i=1; Object *Q=new Objectn; for(i=1;i=n;i+) Qi-1.ID=i; Qi-1.d=1.0*pi/wi; P+=pi; W+=wi; if(W=c) return P;/装入所有物品 /依物品单位重量排序 float f; for( i=0;in;i+) for(int j=i;jn;j+) if(Qi.dQj.d) f=Qi.d; Qi.d=Qj.d; Qj.d=f; Knap K; K.p = new intn+1; K.w = new intn+1; K.x = new intn+1; K.bestx = new intn+1; K.x0=0; K.bestx0=0; for( i=1;i=n;i+) K.pi=pQi-1.ID; K.wi=wQi-1.ID; K.cp=0; K.cw=0; K.c=c; K.n=n; K.bestp=0; /回溯搜索 K.Backtrack(1); K.print(); delete Q; delete K.w; delete K.p; return K.bestp; void main() int *p; int *w; int c=0; int n=0; int i=0; cout请输入背包个数：n; p=new intn+1; w=new intn+1; p0=0; w0=0; cout请输入个背包的价值：endl; for(i=1;ipi; cout请输入个背包的重量：endl; for(i=1;iwi; cout请输入背包容量：c; coutKnapsack(p,w,c,n)endl; 四、运行输出结果： 五、调试和运行程序过程中产生的问题、采取的措施及获得的相关经验教训：0-1背包问题和背包问题不同，0-1背包问