什么是算法将一组项目分解为3个独立的组？

我的教科书中有这个问题：给定一组n个项目，每个项目都有一个不同的值V（i），将项目分成3组的最佳方式是什么，所以具有最高值的组被最小化？给这个最大的团体的价值。什么是算法将一组项目分解为3个独立的组？

我知道如何做这个问题的2堆变种：它只需要在问题上向后运行背包算法。然而，我很困惑如何解决这个问题。任何人都可以给我任何指示？

答：几乎是同样的事情0-1背包，虽然2D

2012-01-06 Richie Li

既然它出现并消失了，这里就是一个贪心失败的例子{100,51,49,40,30,20,10}。最佳答案是完美分割，贪婪地将最大未分配元素应用于最小分组不是。 – ccoakley 2012-01-06 19:13:53

我有同样的教科书。布赖恩迪恩给了我;） – joshim5 2012-01-10 14:48:03

艰难的功课问题。这实质上是3分区问题的优化版本。

它是密切相关的装箱，分区和子集和（，正如你提到的，背包）。然而，它恰好是强烈的NP-Complete，这使它比堂兄弟更难。无论如何，我建议你首先看看动态编程解决方案的相关问题（我会从分区开始，但找到DP解决方案的非维基百科解释）。

更新：我很抱歉。我误导了你。 3分区问题将输入分成3组，而不是3组。我所说的其余部分仍然适用，但重新希望你的变体不是很强的np-complete。

2012-01-06 18:07:59 ccoakley

我已经添加了一些信息的问题。 – 2012-01-06 18:19:51

@RichieLi诚实的问题：你希望我有多少细节不会破坏这个问题？即期望的复发关系是否太多（不是我拥有它，我必须自己解决）？ – ccoakley 2012-01-06 18:23:00

嗯，我会尽力自己解决。它在晚上到期，所以如果我需要更多帮助，我会尽快回复您。 – 2012-01-06 18:28:49

我从数学角度不了解“The Best”，但一种显而易见的方法是在每个组中最初建立一组项目。然后，只要您的组的数量多于期望数量的最终组，请提取具有最低值的两个组，然后将它们合并为一个新组，并添加回集合中。这与霍夫曼压缩树如何构建相似。

实施例：

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

2012-01-06 18:12:51

我们还没有了解到这一点，所以我不认为我应该在这个问题上使用它。 – 2012-01-06 18:15:28

采摘尼特：贪婪方法在霍夫曼情况下是最优的（对于固定字母的可变长度编码）。只有当问题中的数字分布得很好时（我不能比“很好地”这个词更精确），它才能合理地进行分区。鉴于这个问题被标记为“动态编程”，我猜测这个任务的目的不是使用贪婪技术。 – ccoakley 2012-01-06 18:17:25

设f [i] [j] [k]表示是否有可能具有在所述第一组值j和在第二组值k，与第一个项目。

所以我们有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，更新你的答案取决于你如何定义相当。

2012-01-08 04:02:21 Topro

但是第i个项目也可以进入第3个集合，所以我认为它应该是f [i] [j] [k] = f [i-1] [jv [i]] [k]或f [i -1] [j] [kv [i]]或f [i-1] [j] [k]'。 – 2012-12-18 16:26:52

另外，为了解释它，当考虑一些i，j，k的解，其中f [i] [j] [k] = True时，可以使用s [i] - j来计算第三组的权重 - k，其中s [i]是前i项的权重之和（以开始时的线性时间进行预先计算）。 – 2012-12-18 16:28:16

@j_random_hacker是的，你是对的。我的错 – Topro 2012-12-19 04:50:33

回答