TC官方合作论坛

标题: 高手进,求一个平均分配背包物品的算法 [打印本页]

作者: chiayo 时间: 2015-6-3 21:22
标题: 高手进,求一个平均分配背包物品的算法
a b c d e五个商品
数量 a=20,b=35,c=10,d=13,e=69
价格 a=30,b=33,c=120,d=350,e=112
将这5个商品放入4个背包
4个背包内商品的价格在总价的1/4上下,不需要很精确
求每个背包放入商品的品种和数量

作者: 言术 时间: 2015-6-3 21:53
我说下我想到的思路，把每个价格数量相乘，得到每个物品总价，然后把每个物品总价进行大小排序，排完序把个数减去背包数，余数为小数，把这小数分别加到次等的小数中
数量 a=20,b=35,c=10,d=13,e=69
价格 a=30,b=33,c=120,d=350,e=112
总a=600，b=1155，c=1200，d=4550，e=7728
a+b，c，d，e
这是我所能想到的，就这些吧

作者: kimcerhak 时间: 2015-6-4 08:21
什么叫上下,,不超过4分之一的意识吧上下那就没有界限了

作者: chiayo 时间: 2015-6-9 12:59

kimcerhak 发表于 2015-6-4 08:21
什么叫上下,,不超过4分之一的意识吧上下那就没有界限了

问题解决了,将物品按照价格从大到小的顺序排序,然后从大到小一个个放入4个背包,同时比对价格合计有么有超过4分之1,但是最后一个背包的价格合计要在4分之1的价格+最后一个商品的价格,因为有时会发生4个背包的价格都小于4分之1,但剩余空间能放入的价格都大于最后一个商品的情况,导致死循环

作者: chiayo 时间: 2015-6-9 13:00

言术发表于 2015-6-3 21:53
我说下我想到的思路，把每个价格数量相乘，得到每个物品总价，然后把每个物品总价进行大小排序，排完序把个 ...

这个思路不对,后来我自己解决了

欢迎光临 TC官方合作论坛 (http://bbs.52tc.co/)