求教一个算法问题。

该用户从未签到

4 主题	11 好友	1323 积分

Continue

积分: 1323

发表于 2013-9-24 17:26:46 | 显示全部楼层 |阅读模式

╱人◕‿‿◕人╲定下契约

您需要登录才可以下载或查看，没有账号？╱人◕‿‿◕人╲订下契约（注册新用户）

本帖最后由 pefectdream 于 2013-9-24 18:08 编辑

某人的饭量为T，有n份体积分别为t1, t2, ... tn的美食，能否从n份美食中挑选若干份，使得恰好吃饱，也不浪费食物，求出所有满足条件的选择。

例：
请输入饭量T：T=10
请输入食品份数n：n=6
请输入6份食品的体积：1, 8, 4, 3, 5, 2
输出：可得到四组解：(1,4,3,2); (1,4,5); (8,2); (3,5,2)。

希望大神来帮助看下，怎么实现。

签名被小宅喵吞掉了~~~~(>_<)~~~~

使用道具举报

foodszhu

该用户从未签到

30 主题	127 好友	2万积分

技术宅认证程序员

重度中二患者

积分: 28325

发表于 2013-9-25 01:09:32 | 显示全部楼层

仍然是动态规划01背包的变种啊。。。
比如F[M][i] 里存储的便是 M总量下第i个之后恰好吃饱食品组成个数
那么F[M+ti][i - 1] 就是吃第i个的个数F[M][i]，同时加上不吃的个数F[M][i]
F[M + ti][i - 1] = F[M + ti][i](不变) + F[M][i](将ti写在其后) (不是单纯的加,而是组合)
F[0][i] = {0}
F[i][N] = {0}
不存在的默认为{0}
最后一路倒推就可以得到结果
对于上面例子解析
F[2][5] = F[2][6] + F[0][6] = { 2 }
F[7][5] = F[7][6] + F[2][6] = {0} + {2, 5} = {2, 5}
F[2][4] = {2}
F[3][4] = {3}
F[5][4] = F[5][5] + F[2][5] = {0} + {2} = {2， 3}
F[10][4] = F[10][5] + F[7][5] = {2, 5, 3}
......
循环遍历T的所有值
并且可以用循环数组节省内存
在T不是非常大的情况下这样还是可以的
T如果非常大，就要考虑其他算法了

等死星人

回复支持反对

使用道具举报