一个背包问题的程序

mcemil

super easy.
不过我想说的是，不要一看到背包、一看到往包里放东西就是背包问题了，这题和配报没一毛钱关系。
随手一写，不过只能求出装配种数，不能打印具体装配形式。保留中间过程太烦了

int dp[11][6]; int a[200]={1,2,4,5,8}; int solve() { &nbsp;&nbsp;&nbsp;&nbsp;memset(dp,0,sizeof(dp)); &nbsp;&nbsp;&nbsp;&nbsp;int i,j,k; &nbsp;&nbsp;&nbsp;&nbsp;dp[0][0]=1; &nbsp;&nbsp;&nbsp;&nbsp;for(i=0;i<5;i++) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for(j=10-a[i];j>=0;j--) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for(k=5;k>=1;k--) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;dp[j+a[i]][k]+=dp[j][k-1]; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;int ret=0; &nbsp;&nbsp;&nbsp;&nbsp;for( i=1;i<=5;i++)ret+=dp[10][i]; &nbsp;&nbsp;&nbsp;&nbsp;return ret; }

[ 本帖最后由 mcemil 于 2009-4-24 17:17 编辑 ]