什么是将一组项目公平地分成3个独立组的算法？

Question

我的教科书中有这个问题:给定一组n个项目,每个项目都有一个不同的值V(i),将项目分成3组的最佳方法是什么,以便将具有最高值的组最小化？给出这个最大的组的价值.

我知道如何做这个问题的2堆变体:它只需要在问题上向后运行背包算法.但是,我很困惑如何解决这个问题.任何人都可以给我任何指示吗？

答:与0-1背包几乎完全相同,尽管是2D

Answer 1

家庭作业问题很棘手。这本质上是三分区问题的优化版本。

http://en.wikipedia.org/wiki/3-partition_problem

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

更新：我道歉。我误导你了。3 分区问题将输入分成 3 个集合，而不是 3 个集合。我所说的其余内容仍然适用，但重新希望您的变体不是强 np 完全的。