回溯法解决背包问题.doc

发布时间：2022-06-12 发布人：admin 分类：说明书资料大小：0.03M 资料格式：doc 举报版权申诉

c79771ee-bc1d-498b-8255-96996ab1d991.doc.pdf-第1页.png

第1页 / 共3页

c79771ee-bc1d-498b-8255-96996ab1d991.doc.pdf-第2页.png

第2页 / 共3页

c79771ee-bc1d-498b-8255-96996ab1d991.doc.pdf-第3页.png

第3页 / 共3页

文本预览

#include #include using namespace std; class Knap { friend int Knaspack(int *,int *,int ,int ); public : int Bound(int i); void Backtrack(int i); int c; int n; int *w; int *p; int cw; int cp; int bestp; }; void Knap::Backtrack(int i) { if(i>n){ bestp=cp; return ; } if(cw+w[i]<=c) { cw+=w[i]; cp+=p[i]; Backtrack(i+1); cw-=w[i]; cp-=p[i]; } if(Bound(i+1)>bestp) Backtrack(i+1); } 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) return b; b+=p[i]*cleft/w[i]; } class Object{ friend int Knaspack(int *,int *,int ,int ); public: int operator<=(Object a)const {return (d>=a.d);} int ID; float d; }; int Knapsack(int p[],int w[],int c,int n){ int W=0; int P=0; 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]; } if(W<=c) return P; float f; for(i=0;i

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; return K.bestp; } void main(){ int *p,*w,c,n; cout<<"ÇëÊäÈëÎïÆ·Êý:"; cin>>n; cout<<"ÇëÊäÈë±³°üÊýÁ¿:"; cin>>c; w=new int [n+1]; w[0]=0; cout<<"ÇëÊäÈëÎïÆ·ÖØÁ¿:"; for(int i=1;i<=n;i++) cin>>w[i]; p=new int [n+1]; p[0]=0; cout<<"ÇëÊäÈëÎïÆ·¼ÛÖµ:"; for( i=1;i<=n;i++) cin>>p[i]; cout<<"×îÓÅÖµ:"<

分享到：

赞收藏

资料库

回溯法解决背包问题.doc

相关推荐

课程资源

热门标签

最新资料