Tug Of War Problem Statement :
Given a set of n integers, divide the set in two subsets of n/2 sizes each such that the difference of the sum of two subsets is as minimum as possible. If n is even, then sizes of two subsets must be strictly n/2 and if n is odd, then size of one subset must be (n-1)/2 and size of other subset must be (n+1)/2.
Example :
Given input set of integers : {3, 4, 5, -3, 100, 1, 89, 54, 23, 20}
Here size of given array is 10 so output should be two sets of length 5.
If set 1 consists elements : {45, -34, 12, 98, -1} and
set 2 consists elements : {3, 5, -3, 89, 54}
Then sum of elements of both set 1 and aet 2 will be 148
Code Solution :
def tugOfWar(arr, n, curr_elements, no_of_selected_elements, soln, min_diff, Sum, curr_sum, curr_position):
if (curr_position == n):
return
if ((int(n / 2) - no_of_selected_elements) > (n - curr_position)):
return
tugOfWar(arr, n, curr_elements, no_of_selected_elements, soln, min_diff, Sum, curr_sum, curr_position + 1)
no_of_selected_elements += 1
curr_sum = curr_sum + arr[curr_position]
curr_elements[curr_position] = True
if (no_of_selected_elements == int(n / 2)):
if (abs(int(Sum / 2) - curr_sum) < min_diff[0]):
min_diff[0] = abs(int(Sum / 2) - curr_sum)
for i in range(n):
soln[i] = curr_elements[i]
else:
tugOfWar(arr, n, curr_elements, no_of_selected_elements, soln, min_diff, Sum, curr_sum, curr_position + 1)
curr_elements[curr_position] = False
def tugOfWar1(arr, n):
curr_elements = [None] * n
soln = [None] * n
min_diff = [999999999999]
Sum = 0
for i in range(n):
Sum += arr[i]
curr_elements[i] = soln[i] = False
tugOfWar(arr, n, curr_elements, 0, soln, min_diff, Sum, 0, 0)
print("The first group is: ")
for i in range(n):
if (soln[i] == True):
print(arr[i], end=" ")
print()
print("The second group is: ")
for i in range(n):
if (soln[i] == False):
print(arr[i], end=" ")
print("seperate each input element by a ,")
arr = list(map(int,input("Enter array : ").strip().split(",")))
n = len(arr)
tugOfWar1(arr, n)
0 Comments