将一组项目公平地分成 3 个独立组的算法是什么？
我的教科书上有这样的问题： 给定一组 n 个项目，每个项目都有不同的值 V(i)，将项目分为 3 组以便最小化具有最高值的组的最佳方法是什么？给出这个最大组的值。
我知道如何解决这个问题的 2 堆变体：它只需要在问题上向后运行背包算法。然而，我对如何解决这个问题感到非常困惑。有人能给我任何指点吗？
答案：与 0-1 背包几乎相同，尽管是 2D
I have this problem in my textbook:
Given a group of n items, each with a distinct value V(i), what is the best way to divide the items into 3 groups so the group with the highest value is minimIzed? Give the value of this largest group.
I know how to do the 2 pile variant of this problem: it just requires running the knapsack algorithm backwards on the problem. However, I am pretty puzzled as how to solve this problem. Could anyone give me any pointers?
Answer: Pretty much the same thing as the 0-1 knapsack, although 2D
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
家庭作业问题很棘手。这本质上是三分区问题的优化版本。
http://en.wikipedia.org/wiki/3-partition_problem
密切相关装箱、分区和子集总和（以及，正如您所指出的，背包）。然而，它恰好是强 NP 完全的，这使得它比它的同类更难。无论如何，我建议您首先查看相关问题的动态规划解决方案（我将从分区开始，但找到 DP 解决方案的非维基百科解释）。
更新：我道歉。我误导你了。 3 分区问题将输入分成 3 个集合，而不是 3 个集合。我所说的其余内容仍然适用，但重新希望您的变体不是强 np 完全的。
Tough homework problem. This is essentially the optimization version of the 3-partition problem.
http://en.wikipedia.org/wiki/3-partition_problem
It is closely related to bin packing, partition, and subset-sum (and, as you noted, knapsack). However, it happens to be strongly NP-Complete, which makes it a harder than its cousins. Anyway, I suggest you start by looking at dynamic programming solutions to the related problems (I'd start with partition, but find a non-wikipedia explanation of the DP solution).
Update: I apologize. I have mislead you. The 3-partition problem splits the input into sets of 3, not 3 sets. The rest of what I said still applies, but with the renewed hope that your variant isn't strongly np-complete.
令f[i][j][k]表示是否有可能在第一组中具有值j并且在第二组中具有值k，其中 >第一个项目。
所以我们有 f[i][j][k] = f[i-1][jv[i]][k] 或 f[i-1][j][kv[i]].
最初我们有
f[0][0][0] = True。对于每个
f[i][j][k] = True，更新您的答案取决于您如何定义公平。Let f[i][j][k] denotes whether it is possible to have value j in the first set and value k in the second set, with the first i items.
So we have
f[i][j][k] = f[i-1][j-v[i]][k] or f[i-1][j][k-v[i]].and initially we have
f[0][0][0] = True.for every
f[i][j][k] = True, update your answer depends on how you defines fairly.从数学角度来说，我不知道“最佳”是什么，但一种明显的方法是最初建立一组群体，每组中包含一个项目。然后，只要您的组数多于所需的最终组数，就提取具有最低值的两个组，并将它们组合成一个新组，然后将其添加回集合中。这类似于霍夫曼压缩树的构建方式。
例子：
I don't know about "The Best" mathematically speaking, but one obvious approach would be to build a population of groups initially with one item in each group. Then, for as long as you have more groups than the desired number of final groups, extract the two groups with the lowest values and combine them into a new group that you add back into the collection. This is similar to how Huffman compression trees are built.
Example: