spa*_*ain 8 algorithm
我知道这里谈了很多,但我正在努力解决这个问题.
我们有一组数字,例如[3,1,1,2,2,1],我们需要将它分成两个子集,因此每个总和相等或差异最小.
我见过维基百科条目,这个页面(问题7)和博客条目.
但列出的每个算法只给出YES/NO结果,我真的不明白如何使用它们打印出两个子集(例如S1 = {5,4}和S2 = {5,3,3}).我在这里错过了什么？
Zet*_*eta 4
伪多项式算法旨在提供决策问题的答案，而不是优化问题。但请注意，示例中布尔值表的最后一行表示当前集合的总和可达 N/2。
在最后一行中，取布尔值为 的第一列true。然后您可以检查给定列中集合的实际值是多少。如果集合的总和值为 N/2，则您已找到分区的第一组。否则你必须检查哪一组能够与 N/2 相差。您可以使用与上面相同的方法，这次是针对差异d。
true
归档时间：
13 年，1 月 前
查看次数：
8583 次
最近记录：
9 年，10 月 前