0

我有以下问题：给定一组 N 个整数，将它们分成两个几乎相等的分区，使得较大分区的总和最小。这听起来几乎像经典的分区问题，但有一个例外：偶数可以被 2 整除，并且每一半都可以放在一个单独的分区中。

例如：N = 4 数字：20 5 3 1

结果是：15

解释：第一个数字将被二除，每半放在两个分区之一 => 第一个分区 = 10，第二个分区 = 10。第二个数字将添加到第一个分区 => 第一个分区 = 15。最后两个数字将添加到第二个分区 => 第二个分区 = 14

=> 更大分区的总和（分区一）= 15。

我的想法是对奇数进行递减排序并使用贪心算法开始添加它们，始终保持两个分区之和之间的差异尽可能最佳。在完成奇数之后，剩下的就是取偶数，看看是否将它们完全添加到一个分区中，是否比将它们除以 2 并将每一半添加到这两个分区中的一个分区中更好。

同样对于以下数据集，算法将提供正确答案：N = 2 数字：16 15

=> 将取 15，将其添加到第一个分区，然后取 16，看到将其除以 2 不是最佳的，因此它将添加到第二个分区。

=> 答案将是 16。

如果您能给我提供一组数据，算法无法提供最佳答案，我很感兴趣，如果您能提出任何改进建议，我也将不胜感激。

谢谢！:)

4

3 回答 3

3

我会一次性拆分所有偶数，然后应用经典的分区算法。或者是否有一些次要目标来最小化拆分次数？

于 2011-04-07T18:25:25.737 回答
1

分区问题是 NP 完全的，这意味着不太可能存在多项式时间算法。您修改后的变体也是 NP 完全的；还原到原始版本非常简单。

于 2011-04-07T19:05:42.297 回答
0

为什么不将每个数字分成两半，然后将额外的 1 放入循环分区中的奇数？第二个分区的总和总是较小的。

名单：20 17 6 5 3 0 -1 9999999



P1：10 | 8+1 | 3 | 2 | 1+1 | 0 | -1 | 4999999+1 | ==> 总和是 5000025
P2：10 | 8 | 3 | 2+1 | 1 | 0 | -1+1 | 4999999 | ==> 总和是 5000024

于 2011-04-07T18:33:00.977 回答