Divide array into subsets such that difference of sum is minimum

general
1

Please help me in this problem. I am getting very high complexity …

Divide the array into two subsets S1 and S2 such that abs(sum(S1)-sum(S2)) is minimum and both the sets should have equal number of elements or differ by atmost one.

2 Likes
2

Maybe I’m wrong but this is Knapsack problem, isn’t it?

If value of elements in array is small, you can use pseudo-polynomial time algorithm - http://www.youtube.com/watch?v=wFP5VHGHFdk

3

How will you solve it through Knapsack?

4

Yes it can be solved just like knapsack problem if sum of all elements is reasonably small.

Nice video, but little too long for one problem :slight_smile:

5

So solution via knapsack problem.

Assume, that we have n items and their sum in absolute value is w.

You can write simple recursion function like this. State will be represent by two numbers k and s. k represent number of remaining items, we don’t assign to any subset yet. s represent difference between subset we already create from first n-k elements.

Now we want to process next element. The next element is v. Now if we add to subset with larger sum, than we obtain state (k-1, s+v) because we spend one element and the difference araise by v. If we add it to smaller subset we get state (k-1, abs(s-v)) again from the same reason.

Now we can start this recursion from state (n, 0) - we get all elements left and difference between subsets is 0. The answer will be the smallest s, that we get to state (0, s). Number of states and also time complexity is n.w because the biggest difference can be w. But don’t forget to use memoization.

2 Likes
6

@vikasnitt check my answer

7

Yeah got it now…took some time to understand but finally solved and coded also… Thanks michal27…:slight_smile:

8

you’re welcome :slight_smile: I’m glad, that I could help

9

Is there any method to solve this problem without knapsack?

10

Yes , there can be many solutions. Try on your own or search on internet.

11

You can try all 2^n possibilities and pick the best one. This can be even faster in some cases.

But I don’t see problem with knapsack :slight_smile: it’s just great idea, that can be use pretty well. In a lot of problems you can use this idea without knowing it.