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

Question

我有以下问题:

给定N个对象(N <30)的不同值的多个"k"常数,即k,2k,3k,4k,6k,8k,12k,16k,24k和32k,我需要一个将所有项目分配给M的算法玩家(M <= 6),使得每个玩家获得的对象的总价值尽可能均匀(换句话说,我想以最公平的方式将所有对象分发给所有玩家).

编辑:通过最公平的分配我的意思是任何两个玩家获得的对象的价值之间的差异是最小的.另一个类似的情况是:我有N个不同价值的硬币,我需要在M个玩家之间平分它们; 有时他们并没有完全分开,我需要找到下一个最好的分配案例(没有玩家生气,因为另一个人得到太多钱).

我不需要(伪)代码来解决这个问题(此外,这不是一个功课:)),但我会感谢任何想法或链接到可以解决这个问题的算法.

谢谢!

Answer 1

问题是NP完全的.这意味着无法在合理的时间内确保正确的解决方案.(参见3分区问题,谢谢保罗).

相反,你会想要一个好的近似解决方案生成器.这些通常可以在很短的时间内非常接近最佳答案.我可以推荐模拟退火技术,你也可以用它来解决其他一些NP完全问题.

这个想法是这样的:

1. 随机分配项目.
2. 不断在两个随机玩家之间进行随机交换,只要它使系统更公平,或者只是稍微不公平(详情请参阅维基).
3. 如果你有足够的公平,或者你已经没时间了就停下来.

这个解决方案比许多人建议的"贪婪"算法强大得多.贪婪算法是您不断向"最差"玩家添加最大项目的算法.贪婪失败的测试用例的一个例子[10,9,8,7,7,5,5].

我为你做了一个SA的实现.出于教育目的,严格遵循维基文章.如果你优化它,我会说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的情况提供完美的结果.但是我想你可以同样使用模拟退火方法.