动态规划0-1背包问题(算法实验代码).doc

《动态规划0-1背包问题(算法实验代码).doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验二、0-1背包问题（动态规划）实验代码：#includeintm[20][20];intmin(intw,intc){inttemp;if(wc)temp=w;elsetemp=c;returntemp;}voidknapsack(intv[],intw[],intc,intn){intjmax=min(w[n]-1,c);for(intj=0;j<=jm

2、ax;j++)m[n][j]=0;for(intk=w[n];k<=c;k++)m[n][k]=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(intk=w[i];k<=c;k++)m[i][k]=max(m[i+1][k],m[i+1][k-w[i]]+v[i]);}m[1][c]=m[2][c];if(c>=w[1])m[1][c]=max(m[1][c],m[2][

3、c-w[1]]+v[1]);}voidtraceback(intx[],intw[],intc,intn){for(inti=1;i

4、20-i;}knapsack(v,w,c,n);traceback(x,w,c,n);for(intj=0;j<=20;j++){printf("0为不装包，1为装包:%d",x[j]);}测试结果截图为：