分苹果问题，求助~~

问题：分苹果问题，求助~~
描述:

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

---

解决方案1:

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

解决方案2:

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

解决方案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个人， 要求这里面确定相应的人分到他们需要的苹果的数量，排列组合就算一下即可吧.