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

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

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

更新: 在玩过分支界之后,我现在相信这种方法是优越的,因为它在一秒钟内为n=30,m=6的情况提供了完美的结果。不过,我想你也可以使用模拟退火方法。

一些人提出的贪婪的解决方案似乎是最好的选择,我用一些随机值运行了很多次,每次都是正确的。
如果它不是最优的,那么它至少是非常接近的,并且运行在O(nm)左右(我现在不想费心去做数学)。
C实施:

static List<List<int>> Dist(int n, IList<int> values)
{
    var result = new List<List<int>>();
    for (int i = 1; i <= n; i++)
        result.Add(new List<int>());
    var sortedValues = values.OrderByDescending(val => val);
    foreach (int val in sortedValues)
    {
        var lowest = result.OrderBy(a => a.Sum()).First();
        lowest.Add(val);
    }
    return result;
}

这个怎么样?

排序k值。 命令玩家。

循环K值,将下一个值给下一个玩家。 当你到达玩家的终点时,转身继续向相反方向的玩家提供K值。

重复地将具有最大值的可用对象提供给具有分配给他的对象的最小总值的玩家。

这是Justin Peel答案的直接实现:

M = 3
players = [[] for i in xrange(M)]

values = [10,4,3,1,1,1]
values.sort()
values.reverse()
for v in values:
    lowest=sorted(players, key=lambda x: sum(x))[0]
    lowest.append(v)

print players
print [sum(p) for p in players]

我是一个初学巨蟒的人,但它似乎工作正常。此示例将打印

[[10], [4, 1], [3, 1, 1]]
[10, 5, 5]

30^6不是那么大(少于10亿)。通过每一个可能的分配,并选择一个最公平的衡量你定义。

编辑:

其目的是使用贪婪的解决方案,并在实现上稍作改进,这在C中可能是透明的:

static List<List<int>> Dist(int n, IList<int> values) 
{ 
    var result = new List<List<int>>(); 
    for (int i = 1; i <= n; i++) 
        result.Add(new List<int>()); 
    var sortedValues = values.OrderByDescending(val => val);//Assume the most efficient sorting algorithm - O(N log(N))
    foreach (int val in sortedValues) 
    { 
        var lowest = result.OrderBy(a => a.Sum()).First();//This can be done in O(M * log(n)) [M - size of sortedValues, n - size of result]
        lowest.Add(val); 
    } 
    return result; 
} 

关于这个阶段:

var lowest = result.OrderBy(a => a.Sum()).First();//This can be done in O(M * log(n)) [M - size of sortedValues, n - size of result]

其思想是列表总是被排序(在这个代码中,它是由orderby完成的)。最终,这种排序不会超过o(log(n))——因为我们只需要在排序列表中插入至多一个项目——这应该和二进制搜索一样。 因为我们需要对sortedValues.length times重复这个阶段,所以整个算法在o(m*log(n))中运行。

因此,用词来说,它可以改为: 重复以下步骤,直到完成 Values 价值观: 1。为最小的玩家增加最大的价值 2。检查这个玩家是否还有最小的总数 三。如果是,转到步骤1。 4。将最后一个获得玩家的玩家插入排序玩家列表

步骤4是O(log(n))步骤,因为列表总是被排序的。