Tug of War Problem
What is Tug of War Problem?
In the Tug of War problem, a set of integers is given and our task is to break them into two parts, such that the difference of the sum of two subsets is as minimal as possible. In other words, divide the set into two groups of nearly equal strength to participate in the tug-of-war game. When the size of set is even, it becomes easier to divide it into two parts. Doing this with odd numbers of items will be difficult. Thus, there are some constraints defined for dividing.
If the size of subset N is even, it can be divided into two parts using N/2, but for the odd value of N, the size of one subset must be (N-1)/2, and the size of another subset must be (N+1)/2.
Solving Tug of War using Backtracking Approach
Suppose the given set is of odd size −
Set = {23, 45, -34, 12, 0, 98, -99, 4, 189, -1, 4}
When we distribute the weights to make the difference minimum, then, the resulting subsets will be −
Left: {45, -34, 12, 98, -1}
Right: {23, 0, -99, 4, 189, 4}
The following steps explain how backtracking approach is used to solve tug of war problem −
Start with creating an empty subset, say it as left.
Fill this empty subset with a required number of the elements from the original set. The required number of elements depends on the size of original set. If the size is odd, the subset should be filled with (N-1)/2 elements and if the size is even, the size of subset should be N/2.
Check whether the difference of filled elements follows the given constraints or not. If it follows mark it as a part of the solution.
If the difference is not minimum, try other combinations and update the existing solution.
Once the first subset is filled, the remaining elements will automatically become part of the second subset.
Example
In the following example, we will practically demonstrate how to solve the tug of war problem.
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <limits.h>
#include <math.h>
void tgOfWarSoln(int* weight, int n, bool curr[], int select, bool sol[], int *diff, int sum, int total, int pos) {
//when the pos is covered all weights
if (pos == n)
return;
//left elements must be bigger than required result
if ((n/2 - select) > (n - pos))
return;
tgOfWarSoln(weight, n, curr, select, sol, diff, sum, total, pos+1);
select++;
total += weight[pos];
//add current element to the solution
curr[pos] = true;
//when solution is formed
if (select == n/2) {
//check whether it is better solution or not
if (abs(sum/2 - total) < *diff) {
*diff = abs(sum/2 - total);
for (int i = 0; i<n; i++)
sol[i] = curr[i];
}
} else {
tgOfWarSoln(weight, n, curr, select, sol, diff, sum, total, pos+1);
}
//when not properly done, remove current element
curr[pos] = false;
}
void checkSolution(int *arr, int n) {
bool* curr = (bool*)malloc(n*sizeof(bool));
bool* soln = (bool*)malloc(n*sizeof(bool));
//set minimum difference to infinity initially
int diff = INT_MAX;
int sum = 0;
for (int i=0; i<n; i++) {
//find the sum of all elements
sum += arr[i];
//make all elements as false
curr[i] = soln[i] = false;
}
tgOfWarSoln(arr, n, curr, 0, soln, &diff, sum, 0, 0);
printf("Left: ");
for (int i=0; i<n; i++)
if (soln[i] == true)
printf("%d ", arr[i]);
printf("
Right: ");
for (int i=0; i<n; i++)
if (soln[i] == false)
printf("%d ", arr[i]);
printf("
");
free(curr);
free(soln);
}
int main() {
int weight[] = {23, 45, -34, 12, 0, 98, -99, 4, 189, -1, 4};
int n = 11;
checkSolution(weight, n);
return 0;
}
#include <iostream>
#include <cmath>
#include <climits>
using namespace std;
void tgOfWarSoln(int* weight, int n, bool curr[], int select, bool sol[], int &diff, int sum, int total, int pos) {
//when the pos is covered all weights
if (pos == n)
return;
//left elements must be bigger than required result
if ((n/2 - select) > (n - pos))
return;
tgOfWarSoln(weight, n, curr, select, sol, diff, sum, total, pos+1);
select++;
total += weight[pos];
//add current element to the solution
curr[pos] = true;
//when solution is formed
if (select == n/2) {
//check whether it is better solution or not
if (abs(sum/2 - total) < diff) {
diff = abs(sum/2 - total);
for (int i = 0; i<n; i++)
sol[i] = curr[i];
}
} else {
tgOfWarSoln(weight, n, curr, select, sol, diff, sum, total, pos+1);
}
//when not properly done, remove current element
curr[pos] = false;
}
void checkSolution(int *arr, int n) {
bool* curr = new bool[n];
bool* soln = new bool[n];
//set minimum difference to infinity initially
int diff = INT_MAX;
int sum = 0;
for (int i=0; i<n; i++) {
//find the sum of all elements
sum += arr[i];
//make all elements as false
curr[i] = soln[i] = false;
}
tgOfWarSoln(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;
checkSolution(weight, n);
}
public class Main {
static void tgOfWarSoln(int[] weight, int n, boolean[] curr, int select, boolean[] sol, int[] diff, int sum, int total, int pos) {
//when the pos is covered all weights
if (pos == n)
return;
//left elements must be bigger than required result
if ((n / 2 - select) > (n - pos))
return;
tgOfWarSoln(weight, n, curr, select, sol, diff, sum, total, pos + 1);
select++;
//add current element to the solution
total += weight[pos];
curr[pos] = true;
//when solution is formed
if (select == n / 2) {
//check whether it is better solution or not
if (Math.abs(sum / 2 - total) < diff[0]) {
diff[0] = Math.abs(sum / 2 - total);
for (int i = 0; i < n; i++)
sol[i] = curr[i];
}
} else {
tgOfWarSoln(weight, n, curr, select, sol, diff, sum, total, pos + 1);
}
//when not properly done, remove current element
curr[pos] = false;
}
static void checkSolution(int[] arr, int n) {
boolean[] curr = new boolean[n];
boolean[] soln = new boolean[n];
//set minimum difference to infinity initially
int[] diff = {Integer.MAX_VALUE};
int sum = 0;
for (int i = 0; i < n; i++) {
//find the sum of all elements
sum += arr[i];
//make all elements as false
curr[i] = soln[i] = false;
}
tgOfWarSoln(arr, n, curr, 0, soln, diff, sum, 0, 0);
System.out.print("Left: ");
for (int i = 0; i < n; i++)
if (soln[i] == true)
System.out.print(arr[i] + " ");
System.out.println();
System.out.print("Right: ");
for (int i = 0; i < n; i++)
if (soln[i] == false)
System.out.print(arr[i] + " ");
}
public static void main(String[] args) {
int[] weight = {23, 45, -34, 12, 0, 98, -99, 4, 189, -1, 4};
int n = 11;
checkSolution(weight, n);
}
}
def tgOfWarSoln(weight, n, curr, select, sol, diff, sum, total, pos):
if pos == n:
return
if (n // 2 - select) > (n - pos):
return
tgOfWarSoln(weight, n, curr, select, sol, diff, sum, total, pos + 1)
select += 1
total += weight[pos]
curr[pos] = True
if select == n // 2:
if abs(sum // 2 - total) < diff[0]:
diff[0] = abs(sum // 2 - total)
for i in range(n):
sol[i] = curr[i]
else:
tgOfWarSoln(weight, n, curr, select, sol, diff, sum, total, pos + 1)
curr[pos] = False
def checkSolution(arr, n):
curr = [False] * n
soln = [False] * n
diff = [float('inf')]
sum = 0
for i in range(n):
sum += arr[i]
curr[i] = soln[i] = False
tgOfWarSoln(arr, n, curr, 0, soln, diff, sum, 0, 0)
print("Left: ", end="")
for i in range(n):
if soln[i] == True:
print(arr[i], end=" ")
print()
print("Right: ", end="")
for i in range(n):
if soln[i] == False:
print(arr[i], end=" ")
weight = [23, 45, -34, 12, 0, 98, -99, 4, 189, -1, 4]
n = 11
checkSolution(weight, n)
Output
Left: 45 -34 12 98 -1 Right: 23 0 -99 4 189 4
