Balanced Partition Problem – Finding the minimized sum between two partitions of a set of positive integers
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 !
What about “minimize |S2 – 2*S1|” partition problem?
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!
Que fórmula você usou para saber que existem 23 maneiras de dividir os números em dois grupos??
What formula you used to know that there are 23 ways to divide the numbers into two groups?
Reblogged this on shoutcry.
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];
}
}
}
}