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.
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]
.