Saturday, August 6, 2011

Balanced Partitions:

Suppose you are given an array of n integers {a1,……, an} between 0 and M. Give an algorithm for dividing these integers into two sets x and y such that the difference of the sum of the integers in each set, is minimized.

For example, given the set {2,3,2,7,9}, you can divide it into {2, 2, 7} (sums to 11) and {3; 9} (sums to 12) for a difference of 1.

Recursion Relation: Consider just the set of the numbers {a1,…..,aj}. What sums can we make with that set or subsets of it? We can make

  • Any sums we could make with a subset of {a1,….,aj-1}
  • Any sums we could make with a subset of {a1,….,aj-1} + aj

So: Let Cij be 1 if a subset of {a1,…..,ai} adds to j and 0 otherwise. The recursion relation for Cij is


We find the value of j, let it be b, closest to


such that Cnj = 1. The minimum difference is 2(T - b).
Running Time: We need only let j go to nM since the integers are bounded. Therefore, the size of C is n2M and filling it in takes O(1) per entry for a total running time of O(n2M).

A dynamic programming solution to this problem is provided in this video tutorial by Brian C. Dean. It is problem number 7.

Firstly this algorithm can be viewed as knapsack problem where individual array elements are the weights and half the sum as total weight of the knapsack.

1.take a solution array as boolean array sol[] of size sum/2+1

2. For each array element,traverse the array and set sol [j] to be true if sol [j - value of array] is true

3.Let halfsumcloser be the closest reachable number to half the sum and partition are sum-halfsumcloser and halfsumcloser.

4.start from halfsum and decrease halfsumcloser once everytime until you find that sol[halfsumcloser] is true

No comments: