Skip to content

Balanced Partition Problem – Finding the minimized sum between two partitions of a set of positive integers

February 10, 2011

In Balanced Partition problem,you have a set of n integers each in the range 0 … K. Partition these integers into two subsets such that you minimize |S1 – S2|, where S1 and S2 denote the sums of the elements in each of the two subsets.

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

The Balanced Partition problem is a variation of the Partitioning problem Which is NP complete. In partitioning problem the objective is to decide whether a given multiset of integers can be partitioned into two “halves” that have the same sum.

There are many ways to solve this problem.

One approach was the way of doing a differencing heuristic similar to what Kamarkar-karp did to solve the partition problem. The Analysis of Kamarkar-Karp can be found at the link.The differencing algorithm at each step removes two numbers from the set and replaces them by their difference.

To get a detail understanding of this problem and why the Kamarkar-Karp approach is not suitable for all cases is described here by American Scientist article by Brian Hayes

Stephan Mertens in this paper describes a optimized algorithm that combines the balanced largest differencing method (BLDM) and Korf’s complete Karmarkar-Karp algorithm.

Algorithm:
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

import java.io.*;
import java.util.*;
 
public class balpart 
{
	public static void main (String [] args) throws IOException 
	{
        
		int sum = 0;
		System.out.println("Enter the number of array elements");
		Scanner input = new Scanner(System.in);
		int N = input.nextInt();
		int[] array = new int[N];
		System.out.println("Enter the Positive elements of the array");
		for(int member = 0; member < N ; member++)
		{
			array[member] = input.nextInt();
			sum += array[member];		
		}
      
             	boolean [] sol = new boolean [sum / 2 + 1];
        
        	sol [0] = true;//empty array
        	for (int i : array) 
		{
        		for (int j = sum / 2; j >= i; j--) 
			{
                		if (sol [j - i]) 
				sol [j] = true;
            		}
        	}
                     
        	int halfsumcloser = sum / 2;
        	for (; !sol [halfsumcloser]; halfsumcloser--);
		System.out.println ("The Minimum sum After partioning the array is :" +((sum - halfsumcloser) - halfsumcloser));
         
    	}
}

OUTPUT:

labuser@ubuntu:~$ java balpart
Enter the number of array elements
10
Enter the Positive elements of the array
2 10 3 8 5 7 9 5 3 2
The Minimum sum After partioning the array is :0

labuser@ubuntu:~$ java balpart
Enter the number of array elements
2
Enter the Positive elements of the array
1
5
The Minimum sum After partioning the array is :4

There are further question that we can pose here.

A). In the easiest hard problem article author states that for input
2 10 3 8 5 7 9 5 3 2

there are 23 ways to divide up the numbers into two groups with exactly equal sums
one such partition is [2 5 3 10 7] [2 5 3 9 8]

So can we integrate into this algorithm a method to find the total different ways to make a balanced partition.

B) Can we find the exact partition elements?

The above algorithm takes lot of time on huge numbers resulting in large sums.So again we end up with a not so good algorithm.

One Related article i have already written is Algorithm to implement “Equal Sum Subsets” – For a sequence of numbers, find a subset[s](same order as original sequence) in which each subset has the same smallest sum

That’s it for now. I hope to present more articles on partition problem and its variants

Thanks for Reading !

About these ads
6 Comments
  1. Hudson permalink

    What about “minimize |S2 – 2*S1|” partition problem?

  2. Ah Sir can you pls solve this problem pls!
    How much space does 2 HDD partitions need from a 500 gigabyte HDD to create a balance HDD!
    Thanks!

  3. Que fórmula você usou para saber que existem 23 maneiras de dividir os números em dois grupos??

  4. What formula you used to know that there are 23 ways to divide the numbers into two groups?

  5. Reblogged this on shoutcry.

  6. Ayodeji permalink

    It could be solve as such too

    public class Partition {

    static int[] arr = {2, 10, 3, 8, 5, 7, 9, 5, 3, 2};//{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11};
    static int[] pat;
    static int right;
    static int left = 0;
    static int sumLeft, sumRight;
    static int j, k;

    static public void main(String[] args) {
    Arrays.sort(arr);

    right = arr.length – 1;
    pat = new int[arr.length];

    if (arr.length % 2 == 0) {
    calcEven();
    } else {
    calcOdd();
    }
    sumUpPartion();
    System.out.println(“Left Partition: ” + sumLeft + “\nRight Partition: ” + sumRight);
    System.out.println(“Minimum diff: ” + Math.abs(sumLeft – sumRight));

    }

    static void calcEven() {
    for (int i = 0; i < arr.length; i += 2) {
    j = arr[i];
    k = arr[i + 1];
    sumUpPartion();
    if (sumLeft <= sumRight) {
    pat[left++] = Math.max(j, k);
    pat[right--] = Math.min(j, j);
    } else {
    pat[left++] = Math.min(j, k);
    pat[right--] = Math.max(j, k);
    }
    }
    }

    static void calcOdd() {
    int temp = arr[0];
    arr[0] = arr[arr.length - 1];
    arr[arr.length - 1] = temp;
    for (int i = 0; i < arr.length – 1; i += 2) {
    j = arr[i];
    k = arr[i + 1];
    sumUpPartion();
    if (sumLeft sumRight) {
    pat[right--] = arr[arr.length - 1];
    } else {
    pat[left++] = arr[arr.length - 1];
    }

    }

    static void sumUpPartion() {
    sumLeft = 0;
    sumRight = 0;
    int i, n;

    int m = pat.length / 2;
    if (arr.length % 2 == 0) {
    for (i = 0, n = m; i < m || n < pat.length – 1; i++, n++) {
    sumLeft += pat[i];
    sumRight += pat[n];
    }
    } else {
    for (i = 0, n = m; i < m || n < pat.length; i++, n++) {
    //System.out.println(i + " " + j);
    sumLeft += pat[i];
    sumRight += pat[n];
    }
    }
    }
    }

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: