关于分配不同价值对象的算法的建议 [英] Suggestion on algorithm to distribute objects of different value
问题描述
我有以下问题:
给定N个对象(N <30)，它们的值不同，是"k"常数的倍数，即k，2k，3k，4k，6k，8k，12k，16k，24k和32k，我需要一种算法来分配将所有项目分配给M个玩家(M <= 6)，以使每个玩家获得的对象的总价值尽可能的均匀(换句话说，我想以最公平的方式将所有对象分配给所有玩家) ).
Given N objects (N < 30) of different values multiple of a "k" constant i.e. k, 2k, 3k, 4k, 6k, 8k, 12k, 16k, 24k and 32k, I need an algorithm that will distribute all items to M players (M <= 6) in such a way that the total value of the objects each player gets is as even as possible (in other words, I want to distribute all objects to all players in the fairest way possible).
通过最公平的分配，我的意思是任何两个玩家获得的对象的值之间的差异是最小的. 另一个类似的情况是:我有N个面额不同的硬币，我需要将它们平均分配给M个玩家；有时他们的分配不完全一致，我需要找到下一个最佳分配情况(没有玩家生气，因为另一个人的钱太多了.)
By fairest distribution I mean that the difference between the value of the objects any two players get is minimal. Another similar case would be: I have N coins of different values and I need to divide them equally among M players; sometimes they don't divide exactly and I need to find the next best case of distribution (where no player is angry because another one got too much money).
我不需要(伪)代码来解决这个问题(而且，这不是一项家庭作业:))，但是我将不胜感激任何想法或指向可以解决此问题的算法的链接.
I don't need (pseudo)code to solve this (also, this is not a homework :) ), but I'll appreciate any ideas or links to algorithms that could solve this.
谢谢！
推荐答案
该问题是NP完全问题.这意味着无法确保在合理的时间内提供正确的解决方案. (感谢Paul，请参见 3-分区问题).
The problem is strongly NP-complete. This means there is no way to ensure a correct solution in reasonable time. (See 3-partition-problem, thanks Paul).
相反，您将需要一个好的近似解决方案生成器.这些通常可以在很短的时间内非常接近最佳答案.我可以推荐模拟退火技术，您也可以将其用于大量其他NP完全问题.
Instead you'll wanna go for a good approximate solution generator. These can often get very close to the optimal answer in very short time. I can recommend the Simulated Annealing technique, which you will also be able to use for a ton of other NP-complete problems.
想法是这样的:
- 随机分配物品.
- 不断地在两个随机玩家之间进行随机交换，只要它使系统更加公平，或者公平程度就稍差一点(有关详细信息，请参阅Wiki).
- 当您有足够的公平或已用完时间时停止.
此解决方案比许多人建议的贪婪"算法要强大得多.贪婪算法是您不断将最大的项添加到最差"播放器的算法.贪婪失败的测试用例示例是[10,9,8,7,7,5,5].
This solution is much stronger than the 'greedy' algorithms many suggest. The greedy algorithm is the one where you continuously add the largest item to the 'poorest' player. An example of a testcase where greedy fails is [10,9,8,7,7,5,5].
我为您实施了SA.出于教育目的，它严格遵循Wiki文章.如果您对其进行优化，我想说100倍的改进并不是不现实的.
I did an implementation of SA for you. It follows the wiki article strictly, for educational purposes. If you optimize it, I would say a 100x improvement wouldn't be unrealistic.
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的情况提供了完美的结果.但是我想您也可以使用模拟退火方法.
Update: After playing around with Branch'n'Bound, I now believe this method to be superior, as it gives perfect results for the N=30, M=6 case within a second. However I guess you could play around with the simulated annealing approach just as much.
这篇关于关于分配不同价值对象的算法的建议的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
