分苹果问题,求助~~

有五个人,每个人拥有的苹果数量不同,这五个人要如何相互分配,才能在分配后使得各自的苹果数目和平均值的差值小于等于1,求算法~~

阅读 4.7k
3 个回答

对这个 5 个人的苹果个数进行求和, 和记为 sum, 剩下的只有 5种情况:

  • 5 取余 == 0, 大家都是平均分配,皆大欢喜
  • 5 取余 == 1, 多出来一个随便给谁都可以, C(5,1) = 5
  • 5 取余 == 2, 多出来的两个不能给同一个人,否则就不满足 <=1的限制了, 所以 C(5,2)= 10
  • 5 取余 == 3, 同理 C(5,3) = 10
  • 5 取余 == 4, C(5,4)= 5

========= update ========
我忘记考虑了另外一种情况, 你说的只是 <=1 不一定大家都是在 平均值 之上,这种情况比较复杂了:

  • 5 取余 == 0, 大家都是平均值了,但是只有符合 <=1 的条件, 就可以从 5 个人中最多挑选 2 人使他们的苹果数量比平局值 -1:

    • 为什么是两个人呢? 你想啊,如果是 3 人的话,就得把这多来的 3 个苹果, 不能分给自己,要分给剩下的两个人,很明显这不符合 <=1 的原则 (根据 组合记数)

剩下的你自己考虑下吧, 建议找本 <组合数学> 看下

============update2========
我又想到了一种解法,可能对于推广到更多人数的时候复杂度会有点高 O(3^n),应该是没有遗漏的:

  • 首先由于 <=1 的限制,所有对于每个人的苹果数量只会有 3 种状态: 1.比平均数少1 2.等于平均数 3.比平均数多1
  • 可以创造一个 有向图, 构造原点(s), 汇点(e)
  • 然后就是每种状态和其他状态之间连边,每个人 3 种状态, 也就是说两个人之间会有 9 条边, 按照顺序排下来就好, 没有必要任意两个人之间都连边,因为最后的结果是计算排列数嘛,边上的权重为相应的苹果数量
  • 然后对这个有向图跑一遍 深搜(dfs) 或者 广搜(bfs) --> (s->e), 最后满足权重之和==总苹果数 就是正确的方案
  • 对于上面计算出来单一的方案, 最后肯定是里面苹果数量大于平均数的给小于平均数的人(注意: 初始的苹果状态和最后想要获得到的方案的差别),现在问题就相当于 sum的苹果数量,分给n1个人, 要求这里面确定相应的人分到他们需要的苹果的数量,排列组合就算一下即可吧.

每个人将自己手中的苹果分成五份,每人拿走一份。这样就相当于大家手上的苹果都是等量的了吧?然后大家手上的苹果也是平均值了吧?
然后
大家等量的 - 平均值 = 0
接着
0 <= 1
这样算,行么???当然,前提是每个人手中的苹果刚好是5的倍数,否则那不是得削苹果了?

5个数求和 = sum
每人sum/5个? 余下的随便一人一个?

撰写回答
你尚未登录,登录后可以
  • 和开发者交流问题的细节
  • 关注并接收问题和回答的更新提醒
  • 参与内容的编辑和改进,让解决方法与时俱进
推荐问题
宣传栏