一个背包问题的程序

路人乙，在路上

题目为：
一个包的容量为10kg，现有五种货物分别为：1，2，4，5，8kg，问有哪些装包方法？要求输出为{1，4，5}；{2，8}

南无小和尚

贪心或者动态规划好像可以解决

qinghaiyin

可不可以把符合那个问题要求的具体c/c++程序写一下啊？谢谢

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 编辑 ]

qinghaiyin

呵呵，终于看到一个强人了哈，你可不可以把那个程序完善一下把具体的装配形式也弄出来啊？
发到我的邮箱qinghaiyin123@qq.com
因为我急用，谢谢了哈！

cugb_cat

原帖由 qinghaiyin 于 2009-4-24 18:01 发表
呵呵，终于看到一个强人了哈，你可不可以把那个程序完善一下把具体的装配形式也弄出来啊？
发到我的邮箱qinghaiyin123@qq.com
因为我急用，谢谢了哈！

你给多少钱啊？