algorithmdynamic-programminggreedy

Balanced Partition greedy approach


I was looking at the balanced partitioning problem on en.wikipedia and in an MIT collection of DP notes (problem 7).

The problem basically asks to partition a given array of numbers into 2 subsets (S1 and S2) such that absolute difference between the sums of numbers is S1 ans S2 |sum(S1) - sum(S2)| needs to be minimum. One thing I didn't understand is why doesn't anyone suggest greedy approach:

def balanced_partition(lst):
    idx = 0
    S1 = 0
    S2 = 0
    result_partition=[None]*len(lst)
    while idx < len(lst):
        new_S1 = S1 + lst[idx]
        new_S2 = S2 + lst[idx]
        if abs(new_S1 - S2) < abs(new_S2 - S1):
            result_partition[idx] = 1
            S1 = new_S1
        else:
            result_partition[idx] = 2
            S2 = new_S2
        idx += 1
    print("final sums s1 = {S1} and s2 = {S2} ".format(S1=S1, S2=S2))
    return result_partition

What is wrong with my approach? It seems to pass all the test cases I can come up with.


Solution

  • The simple counterexample is [1,1,1,1,1,1,6]. The greedy approach will spread the ones between the two sets, while the optimal solution is [1,1,1,1,1,1],[6].