hard?

Given a list of n positive integers (n even), divide the list into two sublists such that the difference between the sums of the integers in the two sublists is minimized. Would this be a NP-complete problem or a NP-hard problem?

---

TL;DR - it's np hard.

this is the optimization version of the partition problem. the partition problem is deciding if a given list of positive integers can be divided into 2 subsets so that the sums of the subsets are equal. the optimization version asks for the minimized difference (like you asked).

the partition problem is np-complete but the optimization is np hard.

you can read more on these problems in wiki: https://en.wikipedia.org/wiki/Partition_problem

链接地址: http://www.djcxy.com/p/39942.html

上一篇: 装配TensorForestEstimator时，TensorFlow崩溃

下一篇: 硬？