分配不同价值物品的算法建议

Question

分配不同价值物品的算法建议

7

我有以下问题：

给定N个不同价值的物品（N < 30），它们都是“k”常数的倍数，例如：k、2k、3k、4k、6k、8k、12k、16k、24k和32k。我需要一种算法将所有物品分配给M个玩家（M <= 6），使每个玩家得到的物品总价值尽可能均匀（换句话说，我想以最公平的方式将所有物品分配给所有玩家）。

编辑：所谓最公平的分配是指任意两个玩家获得的物品价值之间的差异最小。另一个类似的情况是：我有N个不同价值的硬币，我需要平均分配给M个玩家；有时它们不能完全均分，我需要找到下一个最佳分配情况（这样没有玩家会因为另一个玩家得太多钱而生气）。

我不需要（伪）代码来解决这个问题（同时这不是作业 : )），但我会欣赏任何能解决这个问题的思路或算法链接。

谢谢！

- Unknown

定义公平。这是否意味着每个玩家得到的平均值是最大值和最小值之间距离的最小可能值？ - Rubys

我加了一句话来解释我的“公平”（我猜任何人在谈到钱的公平分配时都会理解我的意思:D）。 - Unknown

对于人类来说很简单，但是要在数学上定义它有点棘手，因此我们需要一个一致的定义。 - Rubys

这两个分布是否同样公平？[1]，[2,3]，[4,5]，[20]和[1]，[2,5]，[4,3]，[20]（注意最小值和最大值之间的差异相同）。 - Thomas Ahle

2

我建议将不公平定义为平方和：uf = sum[(avg-p_i)**2 for all p]。这是一个常见的统计公式。如果你最小化 uf，你会得到尽可能接近平均值的数字。 - Thomas Ahle

在你提供的例子中，你选择的在"k"常数之前的系数似乎有一定的规律性。你对那些在k之前的系数值有任何信息或限制吗？（它们必须是整数吗？它们必须相对均匀分布吗？它们必须落在某个特定范围内吗？）这可能会简化算法。 - Amichai

7个回答

2

少数人提出的贪心解法似乎是最佳选项，我用一些随机值多次运行它，每次看起来都能得到正确的结果。
如果不是最优解，至少非常接近，并且它的运行时间大约为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;
}

- Rubys

我喜欢这个和Python解决方案长度大致相同的方式。 - Rubys

我认为贪心算法解法几乎是最优的，因为所使用的值的位数很少。基本上，你可以忽略 k，然后这些数字用 5 位表示。对于二分问题，位数与要划分的项数的比率需要低于 .96。在我们的问题中，我们有一个 5/30 = .1666666667 的比率。然而，我们有更高数量的分区，所以临界比率会不同，但我感觉这么低的比率使用贪心算法可以得到好的结果。 - Justin Peel

1

这是 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]

我是Python的初学者，但似乎它能正常工作。这个例子将会打印出来。

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

- Duddle

尝试这个：10,9,8,7,6,6,6,5 - Thomas Ahle

1

这样怎么样：

按k值排序。按玩家排序。

循环遍历k值，将下一个值给下一个玩家。当到达玩家末尾时，掉头并继续以相反方向将k值分配给玩家。

- Randy

这是一个不错的开始，但需要进行一些修改。例如，请考虑以下情况：3名玩家，其值分别为10、4、3、1、1、1。你的算法将得出11、5、4，而显然更平衡的结果应该是10、5、5。 - Rubys

1

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

- Justin Peel

我曾经考虑过类似的方法，但由于我在数学和算法方面非常生疏，我不知道像这样给出物品是否会导致最佳分配。这似乎与Randy / Rubys建议的相当相似。 - Unknown

@Paul所提到的文章：en.wikipedia.org/wiki/Partition_problem表明，在M=2且对象值随机分布的情况下，差异将高达总和的1/3。（最大值将是总和的1/2的4/3） - Thomas Ahle

0

编辑：

目的是使用贪心算法的小改进来实现，这在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 次，整个算法的运行时间为 O(M * log(n))。

因此，用语言表述可以重新表述为：重复以下步骤，直到完成 Values 值： 1. 将最大值添加到最小的玩家 2. 检查该玩家是否仍具有最小总和 3. 如果是，则返回步骤 1。 4. 将上次获得的最后一个玩家插入到已排序的玩家列表中

第 4 步是 O(log(n)) 步骤 - 因为列表始终保持有序。

- rkellerm

你应该简要介绍一下你的代码是如何工作的。这将使人们更容易理解你的想法。 - Thomas Ahle

此外，请考虑您的解决方案是否解决了所有情况，或者哪些情况没有解决。例如，您可能想考虑M=3时的[6,5,4,3,3,3,3]。 - Thomas Ahle

你是正确的。我希望现在解释得更好了。谢谢！ - rkellerm

0

30 ^ 6并不是很大（小于10亿）。遍历每个可能的分配，并选择按您定义的任何标准最公平的那个。

- user97370

我忘了提到这一点，暴力破解不够快，因为我需要在几秒钟内得到答案。 - Unknown

由于这些值是固定的，所以您只需要进行一次暴力破解！ - Aryabhatta

我不确定我理解如何只做一次... 我有值为k，2k，3k，4k，6k等的对象，但不是每次都是相同的组合！例如，有时我可以尝试分配16k、2k、4k、k、k、k、2k，而另一次则是3k、3k、8k、k。 - Unknown

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Thomas Ahle · Accepted Answer

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

相反，您需要选择一个好的近似解生成器。这些通常可以在很短的时间内非常接近最优答案。我可以推荐模拟退火技术，您还可以将其用于其他许多 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

更新：在尝试了分支定界法后，我现在认为这种方法更优秀，因为它可以在一秒内得出N=30，M=6情况的完美结果。不过，我猜你也可以尝试使用模拟退火方法。