主题：估计也就高手能解决
zhuguiyong
[专家分：0] 发布于 2009-11-13 21:52:00
题目：现有6种杯子，箱子可能放一种，也可能多种。假设1号杯子重量a=2.1克，2号杯子30.5克，3号杯子80.6克，4号杯子50.3克，5号杯子20.4克，6号杯子27.5克。（1-6号杯子最多个数不超过100。）如果我现在我称得总重量X（假如600克），有多少种可能性？算法最优。最好所用时间最短。
回复列表 （共9个回复）
沙发
yansheng [专家分：1530] 发布于 2009-11-14 10:13:00
用for循环不是最优吧！
板凳
swlingling [专家分：0] 发布于 2009-11-16 13:43:00
贪心算法?
4 楼
iAkiak [专家分：8460] 发布于 2009-11-18 21:34:00
递推
count[n][i]表示仅使用前n种杯子，组成总重量为i的不同组合数量
count[n+1][i]=Sigma{j in [0, 100]}( count[n][i-j*weight[n+1]] )
初始count[0][0]=1
复杂度O(n*m*p)，n为杯子种类数，m为一种杯子最多能使用的数量，p为目标总重量
楼主的数据得到819
5 楼
C++军统 [专家分：0] 发布于 2009-12-13 22:48:00
转换成数学问题，列微分方程，用编程来解，这样最优吧
6 楼
shenjinggege [专家分：3260] 发布于 2009-12-14 04:50:00
微分方程？哇哈哈
7 楼
376923432 [专家分：150] 发布于 2009-12-14 18:57:00
能给出程序吗？
觉得你的思路挺好但是想不出具体怎么实现
请指点一下
8 楼
shenjinggege [专家分：3260] 发布于 2009-12-14 19:12:00
http://blog.pfan.cn/wcai/50339.html
看我这篇文章 类似的题目
9 楼
lddetw [专家分：0] 发布于 2012-10-18 10:42:00
学习一下学习一下
[url=http://www.sc115.com/vector]矢量素材[/url],[url=http://www.sc115.com/PPT]PPT模板[/url],[url=http://www.sc115.com]素材中国[/url]
我来回复
您所在位置：社区首页 — C/C++语言讨论区 — 估计也就高手能解决