In this problem a set of integers are given, we have to break them
into two parts, such that the difference of the sum of two subsets is
minimum as possible. So our target is to divide two groups of nearly
equal strength to participate in the Tug of war game.
If the size of subset n is even, it must be divided into n/2, but for
the odd value of n, then the size of one subset must be (n-1)/2, and
size of another subset must be (n+1)/2.
Input and Output
Input:
A set of different weights.
{23, 45, -34, 12, 0, 98, -99, 4, 189, -1, 4}
Output:
The left and right subset to distribute the weights to make the
difference minimum.
Left: {45, -34, 12, 98, -1}
Right: {23, 0, -99, 4, 189, 4}
Algorithm
tugOfWar(weight, n, curr, select, sol, diff, sum, total, pos)
Input − Set of given weights, number of weights, current list, number
of selected items, the difference between two subset sum, the sum of
all items, total in the subset, position of the selected element.
Output − Solution set for selected for left and right subsets.
Begin
if pos = n, then //when all elements are taken
return
if (n/2-select) > (n - pos), then
return
tugOfWar(weight, n, curr, select, sol, diff, sum, total, pos+1)
select := select + 1
total := total + weight[pos]
curr[pos] := true //when item at pos is taken
if select = n/2, then
if difference of (sum/2 and total) < diff, then
diff := difference of (sum/2 and total)
for i := 0 to n, do
sol[i] := curr[i]
done
else
tugOfWar(weight, n, curr, select, sol, diff, sum, total, pos+1)
curr[pos] := false //remove current element if not properly done
End
Example
#include < iostream >
#include < cmath >
using namespace std;
void tugOfWar(int* weight, int n, bool curr[], int select, bool sol[],
int &diff, int sum, int total, int pos) {
if (pos == n) //when the pos is covered all weights
return;
if ((n/2 - select) > (n - pos)) //left elements must be bigger than
required result
return;
tugOfWar(weight, n, curr, select, sol, diff, sum, total, pos+1);
select++;
total += weight[pos];
curr[pos] = true; //add current element to the solution
if (select == n/2) { //when solution is formed
if (abs(sum/2 - total) < diff) { //check whether it is better solution
or not
diff = abs(sum/2 - total);
for (int i = 0; i< n; i++)
sol[i] = curr[i];
}
} else {
tugOfWar(weight, n, curr, select, sol, diff, sum, total, pos+1);
}
curr[pos] = false; //when not properly done, remove current element
}
void findSolution(int *arr, int n) {
bool* curr = new bool[n];
bool* soln = new bool[n];
int diff = INT_MAX; //set minimum difference to infinity initially
int sum = 0;
for (int i=0; i< n; i++) {
sum += arr[i]; //find the sum of all elements
curr[i] = soln[i] = false; //make all elements as false
}
tugOfWar(arr, n, curr, 0, soln, diff, sum, 0, 0);
cout << "Left: ";
for (int i=0; i< n; i++)
if (soln[i] == true)
cout << arr[i] << " ";
cout << endl << "Right: ";
for (int i=0; i< n; i++)
if (soln[i] == false)
cout << arr[i] << " ";
}
int main() {
int weight[] = {23, 45, -34, 12, 0, 98, -99, 4, 189, -1, 4};
int n = 11;
findSolution(weight, n);
}
Output
Left: 45 -34 12 98 -1
Right: 23 0 -99 4 189 4