algorithmnumberspartition-problem

Divide a given set of numbers N in two groups such that their difference of their sum is minimum?

You can exempt atmost one element from the set to acheive the goal. example:-

N=3

the numbers given are = 1,2,5

So,

Set 1 should be :- [1]

Set 2 should be :- [2]

We have excluded 5 as we can acheive a lesser difference without it being in either groups.

N=4

numbers = 1,2,2,5

Set1 = [1,2,2]

Set2 = [5]

What is best algorithm for this? I know that this a NP-complete problem. And I think that brute force would give me the correct solution but I need an algorithm if available.

Solution

  • I know that this a NP-complete problem.

    Not exactly, the partition optimisation problem is even known to be NP-hard.

    And I think that brute force would give me the correct solution but I need an algorithm if available.

    NP-hard means just that there is no known algorithm (to determine the solution) performing better than the brute force method.

    So you'll probably need an approximation, but which one fits your needs only you can know.

    What is best algorithm for this?

    Define "best".