高手进,求一个平均分配背包物品的算法

chiayo

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上下,不需要很精确
求 每个背包放入商品的品种和数量

言术

我说下我想到的思路，把每个价格数量相乘，得到每个物品总价，然后把每个物品总价进行大小排序，排完序把个数减去背包数，余数为小数，把这小数分别加到次等的小数中
数量 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

什么叫上下,,不超过4分之一的意识吧  上下 那就没有界限了

chiayo

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

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

chiayo

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

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