回溯法实验0 1背包问题 C++.doc

《回溯法实验0 1背包问题 C++.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、#include#include#includeintmin(intw,intc){inttemp;if(wc)temp=w;elsetemp=c;returntemp;}voidknapsack(intv[],intw[],intc,intn,int**m)//求最优值{intjmax=min(w[n]-1,c);for(intj=0;j<=jmax;j++)m[n][j]=0;for(i

2、ntjj=w[n];jj<=c;jj++)m[n][jj]=v[n];for(inti=n-1;i>1;i--){//递归部分jmax=min(w[i]-1,c);for(intj=0;j<=jmax;j++)m[i][j]=m[i+1][j];for(intjj=w[i];jj<=c;jj++)m[i][jj]=max(m[i+1][jj],m[i+1][jj-w[i]]+v[i]);}m[1][c]=m[2][c];if(c>=w[1])m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]);cout<<"最优值："<

3、intl=2;l<=n;l++)for(intj=0;j<=c;j++){cout<

4、])?1:0;for(inty=1;y<=n;y++){cout<>n>>c;int*v=newint[n+1];cout<<"Plsinputtheproperty(v[i]):"<>v[i];int*w=newint[n+1];c

5、out<<"Plsinputtheweight(w[i]):"<>w[j];int*x=newint[n+1];m=newint*[n+1];//动态的分配二维数组for(intp=0;p