算法分析之 0_1背包问题回溯法

#include<iostream> 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++) { if(m%10==0) printf("\n"); printf("%-4d",bestx[m]); } printf("\n"); }; 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;//当前解 }; // ************** Bound() 计算上界 ******************************** int Knap::Bound(int i) { int cleft=c-cw;//剩余容量 int b=cp; //以物品单位重量价值递减序装入物品 while(i<=n&&w[i]<=cleft) { cleft-=w[i]; b+=p[i]; i++; } //装满背包 if(i<=n) b+=p[i]/w[i]*cleft; return b; } // ******************** Backtrack() 回溯函数 ************************ void Knap::Backtrack(int i) { if(i>n) { if(bestp<cp) { for(int j=1;j<=n;j++) bestx[j]=x[j]; bestp=cp; } return; } if(cw+w[i]<=c) //搜索左子树 { x[i]=1; cw+=w[i]; cp+=p[i]; Backtrack(i+1); cw-=w[i]; cp-=p[i]; } if(Bound(i+1)>bestp)//搜索右子树 { x[i]=0; Backtrack(i+1); } } class Object { friend 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; Object *Q=new Object[n]; for(i=1;i<=n;i++) { Q[i-1].ID=i; Q[i-1].d=1.0*p[i]/w[i]; //物品 i 单位质量的价值 P+=p[i]; W+=w[i]; } if(W<=c) return P;//装入所有物品 float f; for( i=0;i<n;i++) //依物品单位质量价值排序 for(int j=i;j<n;j++) { if(Q[i].d<Q[j].d) { f=Q[i].d; Q[i].d=Q[j].d; Q[j].d=f; } } Knap K; K.p = new int[n+1]; K.w = new int[n+1]; K.x = new int[n+1]; K.bestx = new int[n+1]; K.x[0]=0; K.bestx[0]=0; 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);//回溯搜索 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<<"请输入背包容量(c)："; cin>>c; cout<<"\n请输入物品的个数(n)："; cin>>n; p=new int[n+1]; w=new int[n+1]; p[0]=0; w[0]=0; cout<<"\n*****物品的价值(p)和重量(w)数据如下*****\n"<<endl; for(i=1;i<=n;i++) { cout<<"请输入第"<<i<<"个物品的价值(p)和重量(w):"; cin>>p[i]>>w[i]; } cout<<"最优解为(bestx)："<<endl; cout<<"最优值为(bestp)："<<endl; cout<<Knapsack(p,w,c,n)<<endl; }