将一组物品公平地分成三组的算法是什么？

Question

8

我在我的教材中遇到了这个问题：给定一个n个项目的组，每个项目都有一个不同的价值V（i），最佳方法是将项目分成3个组，使具有最高价值的组最小化？给出此最大组的值。

我知道如何解决这个问题的两堆变体：只需要在问题上向后运行背包算法。但是，我对如何解决这个问题感到非常困惑。能否有人给我任何指针？

答案：基本与0-1背包相同，尽管是2D。

- Richie Li

由于它出现并消失了，这里有一个贪心失败的例子{100, 51, 49, 40, 30, 20, 10}。最佳答案是完美分割，贪心地将最大的未分配元素应用于最小的组不是最优解。 - ccoakley

我有同样的教科书。Brian Dean 给了我它 ;) - joshim5

3个回答

1

令 f[i][j][k] 表示第一个集合中是否可能有值为 j，第二个集合中是否可能有值为 k，且这些值是由前 i 个元素组成的。

因此我们有 f[i][j][k] = f[i-1][j-v[i]][k] or f[i-1][j][k-v[i]]。

最初我们有 f[0][0][0] = True。

对于每个 f[i][j][k] = True，根据您如何定义“公平”，更新您的答案。

- iloahz

1

但是第i个项目也可以放入第3个集合中，因此我认为应该是 f[i][j][k] = f[i-1][j-v[i]][k] or f[i-1][j][k-v[i]] or f[i-1][j][k]。 - j_random_hacker

1

另外，为了明确表述，当考虑某些 i、j、k 的解决方案时，其中 f[i][j][k] = True，您将使用 s[i] - j - k 计算第三个集合的权重，其中 s[i] 是前 i 个项目的权重总和（在开始时以线性时间预计算）。 - j_random_hacker

0

就数学而言，我不知道哪个是“最好的”，但一个明显的方法是最初建立一个每个组中只有一个项目的群体。然后，在你拥有比最终所需组数更多的组的情况下，提取两个值最低的组并将它们合并成一个新组，然后将其添加回集合中。这类似于如何构建哈夫曼压缩树。

例子：

1 3 7 9 10
becomes
4(1+3) 7 9 10
becomes
9 10 11(1+3+7)

- 500 - Internal Server Error

我们还没有学过这个，所以我不认为我应该在这个问题上使用它。 - Richie Li

1

挑剔一下：在哈夫曼情况下（用于固定字母表的可变长度编码），贪心算法是最优的。如果问题中的数字分布得好（我无法比“好”更精确），则它在分区方面表现合理。鉴于该问题被标记为“动态规划”，我猜测任务的目的不是使用贪心技术。 - ccoakley

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

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

- ccoakley · Accepted Answer

这是一个难题。本质上，这是3分问题的优化版本。

它与装箱、分区和子集求和密切相关（正如您所指出的，背包问题也是如此）。然而，它恰好是强 NP-完全问题，这使得它比其近亲更难。无论如何，我建议您首先查看相关问题的动态规划解决方案（我会从分区开始，但要找到一个非维基百科的DP解释）。

更新：我很抱歉。我误导了你。三分区问题将输入拆分为3个集合，而不是3个集合。我说的其余部分仍然适用，但带着新的希望，您的变体并不是强NP完全问题。