回溯算法解决0-1背包问题(共7页)

1、精选优质文档-倾情为你奉上算法分析与设计实验报告2015-2016年第2学期 实验班级： 学生姓名： 学 号： 指导老师： 信息工程学院实验项目名称：回溯算法解决0-1背包问题 实验日期：2016年 5 月18 日1、 实验类型： 验证性 设计性2、 实验目的掌握01背包问题的回溯算法3、 实验内容及要求给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?4、 实验步骤#include<iostream>using namespace std;class Knap friend int Knapsack

2、(int p,int w,int c,int n );public: void print() for(int m=1;m<=n;m+)cout<<bestxm<<" "cout<<endl;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 Kna

3、p:Bound(int i)/计算上界int cleft=c-cw;/剩余容量int b=cp;/以物品单位重量价值递减序装入物品while(i<=n&&wi<=cleft)cleft-=wi;b+=pi;i+;/装满背包if(i<=n)b+=pi/wi*cleft;return b;void Knap:Backtrack(int i)if(i>n)if(bestp<cp)for(int j=1;j<=n;j+)bestxj=xj;bestp=cp;return;if(cw+wi<=c) /搜索左子树 xi=1;cw+=wi;cp+=p

4、i;Backtrack(i+1);cw-=wi;cp-=pi;if(Bound(i+1)>bestp)/搜索右子树xi=0;Backtrack(i+1);class Objectfriend int Knapsack(int p,int w,int c,int n);public:int operator<=(Object a)const return (d>=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;O

5、bject *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;i<n;i+) for(int j=i;j<n;j+) if(Qi.d<Qj.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.

6、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<<"请输入背包个数："<<endl; cin>>n;p=new intn+1;w=new int

7、n+1;p0=0;w0=0;cout<<"请输入各背包的价值："<<endl;for(i=1;i<=n;i+)cin>>pi;cout<<"请输入各背包的重量："<<endl;for(i=1;i<=n;i+)cin>>wi;cout<<"请输入背包容量："<<endl;cin>>c;cout<<Knapsack(p,w,c,n)<<endl;5、 实验结果1、 实验图形2、 结果分析 输入背包个数为4个,背包价值分别为30 25 26 15,背包重量分别为4 2 3 1,背包的容量分别为1 2 3 4,则得出的背包算法为0 0 0 1，最优值为15。3、实验总结本次的实验过程中，遇到了一些小问题。最终通过百度的方式解决了，同时也让自己了解到所谓回溯法就是指为了避免生成不可能产生最优解的问题状态，要不断地利用限界函数 (bounding function)来处死那些实际上不可能产生所需解的活结点，以此来减少问题的计算量，这种具有限界函数的深度优先生成法就称为回溯法。总之通过本次的算法设计的实验