CODEWITHSUNDEEP
calgorithmgreedydata-partitioning
ZLMN
ZLMN

Reputation: 741

Custom partition problem

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! :)

Upvotes: 0

Views: 813

Answers (3)

pmg
pmg

Reputation: 108988

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.

List: 20 17 6 5 3 0 -1 9999999



P1: 10 | 8+1 | 3 | 2   | 1+1 | 0 | -1   | 4999999+1 |  ==> sum is 5000025
P2: 10 | 8   | 3 | 2+1 | 1   | 0 | -1+1 | 4999999   |  ==> sum is 5000024

Upvotes: 0

abeln
abeln

Reputation: 3759

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.

Upvotes: 1

Ted Hopp
Ted Hopp

Reputation: 234847

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?

Upvotes: 3

Related Questions