对一组价格种类不同的商品进行平均分配的有关问题

对一组价格种类不同的商品进行平均分配的问题
我现在在设计一个程序，是对一组价格不同的商品进行平均分配的问题，要求每个人所分配的商品价格总数和商品个数相差不超过指定的范围。
  比如说现在有一组商品(数量比较大):
  白菜:1元
  萝卜:1.5元
  芹菜:2元
  苹果:3元
  西瓜:2元
  以上商品对2个人平分，要求2个人的个数和所分的商品总价差不多，
  如分成:张三(白菜,萝卜,芹菜) = 4.5,
  李四(苹果,西瓜) = 5.
  再如分成3份:张三(白菜,芹菜) = 3
  李四(萝卜,西瓜) = 3.5
  王五(苹果) = 3  
  个数相差不超过10个，金额相差不超过5000即可.
  请各位大大帮忙！

对于我的而言在数量上平均分问题不大，因为总数和需要分的几个人都已确定，但是在于分给每个人的商品价格加起来总价必须差不多。
对于问题补充下：每个商品的价格基本都不一样，就相当于白菜，萝卜只会出现一次，每种种类不同，价格不同的商品只会出现一次！

[解决办法]
可是如果极端一点
就2个东西
电视机:10000
电灯泡:10
怎么都不可能均分的
[解决办法]
可以这样，先把商品按价格从大到小排序，第一轮先从最贵的商品中每人分配一个，从第二轮开始，先找出最穷的那个人，把余下最贵的那个分配给他，以此类推，循环直到分配完成。

[解决办法]

探讨

可以这样，先把商品按价格从大到小排序，第一轮先从最贵的商品中每人分配一个，从第二轮开始，先找出最穷的那个人，把余下最贵的那个分配给他，以此类推，循环直到分配完成。

[解决办法]
最后这个例子似乎不同了，总算看懂你的意思了。

int[] all = new int[1000]();
这里all包含了所有的欠款单。
先排序下，然后顺序分摊给3人，也就是说all[0]给甲，all[1]给乙，all[2]给丙，all[3]给甲，all[4]给乙，all[5]给丙……
上面仅仅是初始化，要保住每人手里有333单，但是这样价值肯定不会平均。

接下来就是价值优化，不能保住一次到位，但是次数多了肯定会很精确，每次优化后，判断差异，如果差异基本不会有变化，或者差异反而变大，则停止优化。

价值优化核心过程：甲、乙、丙3人中找出2个价值差异最大的人出来，对2人进行交换欠款单操作，计算和平均价值的差异，每次交换确保接近平均价值，如果有一方刚好达到平均价值或者差异在理想范围内，则交换停止，交换采用遍历一方数组的方式循环次数最大333。

循环调用价值优化核心过程，每次调用，会使得价值差缩小，最终满足所需要求。
[解决办法]
呃…… 动态规划吧。。背包问题，见过很多遍了

查看更多 下一篇