algorithm - 分配不同值(value)对象的算法建议

Question

我有以下问题:

给定“k”常量的不同值倍数的 N 个对象(N < 30)，即 k、2k、3k、4k、6k、8k、12k、16k、24k 和 32k，我需要一个算法来分配所有将元素分配给 M 个玩家(M <= 6)，这样每个玩家获得的元素的总值(value)尽可能平均(换句话说，我想以尽可能公平的方式将所有元素分配给所有玩家)。

编辑:我所说的最公平分配是指任何两个玩家获得的元素值(value)之间的差异是最小的。 另一个类似的情况是:我有 N 个不同值(value)的硬币，我需要将它们平分给 M 个玩家；有时他们并没有完全划分，我需要找到下一个最好的分配情况(没有玩家因为另一个人得到太多钱而生气)。

我不需要(伪)代码来解决这个问题(另外，这不是家庭作业 :))，但我会感谢任何可以解决这个问题的想法或算法链接。

谢谢!

Answer 1

问题是强 NP 完全问题。这意味着无法确保在合理的时间内得到正确的解决方案。 (参见 3-partition-problem，感谢 Paul)。

相反，您需要一个好的近似解生成器。这些通常可以在很短的时间内非常接近最佳答案。我可以推荐 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

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