自定义分区问题
我有以下问题：给定一组 N 个整数，将它们分成两个几乎相等的分区，以使较大分区的总和最小。这听起来几乎像经典的分区问题，但有一个例外：偶数可以除以二，并且每一半都可以放置在一个单独的分区中。
例如： 数 = 4 数字：20 5 3 1
结果是：15
解释： 第一个数字将除以二，并将每一半放入两个分区之一=>第一个分区 = 10，第二个分区 = 10。第二个数字将添加到第一个分区 =>第一个分区 = 15。最后两个数字将添加到第二个分区 =>第二个分区 = 14
=>较大分区（分区一）的总和= 15。
我的想法是对奇数进行递减排序，并使用贪心算法开始添加它们，始终保持两个分区总和之间的差异尽可能最佳。完成奇数之后，剩下的就是取偶数，看看将它们完全添加到一个分区是否比将它们除以二并将每一半添加到这两个分区之一更优化。
此外，对于以下数据集，算法将提供正确的答案： N = 2 数字：16 15
=>将取 15，将其添加到第一个分区，然后取 16，发现将其除以二并不是最佳选择，因此会将其添加到第二个分区。
=>答案是 16。
如果您能为我提供一组算法无法提供最佳答案的数据，我很感兴趣，如果您能提出任何改进建议，我也将不胜感激。
谢谢！ :)
I have the following problem: Given a set of N integers divide them into two almost equal partitions in such a way that the sum of the greater partition is minimum. This sounds almost like the classical partition problem with one exception: the even numbers can be divided by two and each half can be placed in a separate partition.
For example:
N = 4
Numbers: 20 5 3 1
The result is: 15
Explanation:
The first number will be divided by two and each half placed in one of the two partitions => first partition = 10, second partition = 10.The second number will be added to the first partition => first partition = 15. The last two numbers will be added to the second partition => second partition = 14
=> the sum of the greater partition(partition one) = 15.
The idea that I have is to sort decreasingly the odd numbers and using a greedy algorithm to start adding them always keeping the difference between the sum of the two partitions as optimal as possible. After finishing with the odd numbers all what is left is to take the even ones and see if adding them entirely to one partition is more optimal than dividing them by two and adding each half to one of those two partitions.
Also for the following set of data the algorithm will provide the correct answer:
N = 2
Numbers: 16 15
=> will take 15, add it to the first partition, then take 16 see that is not optimal to divide it by two thus it will add it to the second partition.
=> the answer will be 16.
I am interested if you can provide me a set of data for which the algorithm will not provide the optimal answer and I would be also be grateful if you could suggest any improvements.
Thanks! :)
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
我会一次性分割所有偶数，然后应用经典的划分算法。或者是否有一些次要目标来最小化分裂次数？
I would just split all the even numbers in one pass and then apply the classical partition algorithm. Or is there some secondary objective to minimize the number of splits?
划分问题是NP完全问题，这意味着多项式时间算法不太可能存在。你修改后的变体也是 NP 完全的；还原到原始版本非常简单。
The partition problem is NP-complete, meaning that a polynomial time algorithm is unlikely to exist. Your modified variant is also NP-complete; a reduction to the original version is quite simple.
为什么不将每个数字分成两半，并在循环分区中为奇数添加额外的 1？第二个分区的总和始终较小。Why don't you divide each and every number in half and put the extra 1 for odd numbers in cycling partitions? The 2nd partition will always have the smaller sum.