自定义分区问题

Question

我有以下问题:给定一组 N 个整数，将它们分成两个几乎相等的分区，使得较大分区的总和最小。这听起来很像经典的分区问题，但有一个异常(exception):偶数可以除以二，每一半都可以放在一个单独的分区中。

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

结果是:15

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

=> 较大分区(分区一)的总和 = 15。

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

此外，对于以下数据集，算法将提供正确答案:N = 2数字:16 15

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

=> 答案将是 16。

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

谢谢! :)

Answer 1

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