分配不同价值对象的算法建议

我有以下问题：

给定 N 个对象（N

编辑：通过最公平的分配，我的意思是任何两个玩家获得的物体的价值之间的差异是最小的。 另一个类似的情况是：我有N个不同价值的硬币，我需要将它们平均分配给M个玩家；有时他们并没有完全分开，我需要找到下一个最佳的分配情况（没有玩家因为另一个玩家得到太多钱而生气）。

我不需要（伪）代码来解决这个问题（而且，这不是家庭作业:)），但我将不胜感激任何可以解决这个问题的想法或算法链接。

Thanks!

该问题是强 NP 完全问题。这意味着无法确保在合理的时间内得到正确的解决方案。 （看3-分区问题 http://en.wikipedia.org/wiki/3-partition_problem，谢谢保罗）。

相反，您会想要一个好的近似解生成器。这些往往可以在很短的时间内非常接近最佳答案。我可以推荐模拟退火 http://en.wikipedia.org/wiki/Simulated_annealing技术，您还可以将其用于解决大量其他 NP 完全问题。

想法是这样的：

1. 随机分配物品。
2. 不断在两个随机玩家之间进行随机交换，只要它使系统更加公平，或者只是稍微不那么公平（有关详细信息，请参阅 wiki）。
3. 当你有足够公平的东西，或者你已经没有时间了，就停下来。

这个解决方案比许多人建议的“贪婪”算法要强大得多。贪婪算法是一种不断向“最穷”玩家添加最大物品的算法。贪婪失败的测试用例的一个例子是[10,9,8,7,7,5,5].

我为你实现了SA。出于教育目的，它严格遵循 wiki 文章。如果你对其进行优化，我会说 100 倍的改进并不是不现实的。

from __future__ import division
import random, math

values = [10,9,8,7,7,5,5]
M = 3
kmax = 1000
emax = 0

def s0():
    s = [[] for i in xrange(M)]
    for v in values:
        random.choice(s).append(v)
    return s

def E(s):
    avg = sum(values)/M
    return sum(abs(avg-sum(p))**2 for p in s)

def neighbour(s):
    snew = [p[:] for p in s]
    while True:
        p1, p2 = random.sample(xrange(M),2)
        if s[p1]: break
    item = random.randrange(len(s[p1]))
    snew[p2].append(snew[p1].pop(item))
    return snew

def P(e, enew, T):
    if enew < e: return 1
    return math.exp((e - enew) / T)

def temp(r):
    return (1-r)*100

s = s0()
e = E(s)
sbest = s
ebest = e
k = 0
while k < kmax and e > emax:
    snew = neighbour(s)
    enew = E(snew)
    if enew < ebest:
        sbest = snew; ebest = enew
    if P(e, enew, temp(k/kmax)) > random.random():
        s = snew; e = enew
    k += 1

print sbest

Update:在尝试了 Branch'n'Bound 之后，我现在相信这种方法更优越，因为它在一秒钟内为 N=30、M=6 的情况提供了完美的结果。不过我想你也可以尝试模拟退火方法。