Design Python Program for Tug of War
In this tutorial, you will learn to design a Python program for the Tug of War.
Python Program for Tug of War
In this problem, we are provided with a set of integers. We then need to break the given set into two different sets in such a way that there is a minimum difference in the sum of two subsets. That is we divide the team into two groups with equal strengths to participate in-game.
Consider total number of people (set) is N.
If N is even – Size of each team = N/2
If N is odd – Size of one team = (N-1)/2 while other contains (N+1)/2
Let us consider a small example :
1 )
Given set = {3, 4, 5, -3, 100, 1, 89, 54, 23, 20}
Here, N= 10 (Even)
Thus team 1 = {4, 100, 1, 23, 20}; Sum = 148
Team 2 = {3, 5, -3, 89, 54}; Sum = 148
2)
Given set = {23, 45, -34, 12, 0, 98, -99, 4, 189, -1, 4}
Here, N= 11 (Odd)
Thus team 1 = {45, -34, 12, 98, -1} ; Sum = 120
Team 2 = {23, 0, -99, 4, 189, 4}; Sum = 121
Algorithm :
Begin if position = n, then return if (n/2-selected) > (n - position), then return TugOfWar(weight, n, current, selected, solution, difference, sum, total, position+1) selected := selected + 1 total := total + weight[position] current[position] := true if selected = n/2, then if difference of (sum/2 and total) < diff, then difference := difference of (sum/2 and total) for i := 0 to n, do solution[i] := current[i] done else TugOfWar(weight, n, current, selected, solution, difference, sum, total, position+1) current[position] := false End
- Initialize the current set as empty. Now there are two solutions for every element, either it will be in the current set or else another subset.
- Considering both possibilities, when current set is full(ie contains N/2 elements) check if it best solution out of all previous solution.
- If yes, update the else discard.
Here is a sample code :
def TOW_Until(array, 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 TOW_Until(array, 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 + array[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: TOW_Until(array, n, curr_elements, no_of_selected_elements, soln, min_diff, Sum, curr_sum, curr_position + 1) curr_elements[curr_position] = False def tugOfWar(array, n): curr_elements = [None] * n soln = [None] * n min_diff = [999999999999] Sum = 0 for i in range(n): Sum += array[i] curr_elements[i] = soln[i] = False TOW_Until(array, n, curr_elements, 0, soln, min_diff, Sum, 0, 0) print("First subset: ") for i in range(n): if (soln[i] == True): print(array[i], end = " ") print() print("Second subset: ") for i in range(n): if (soln[i] == False): print(array[i], end = " ") if __name__ == '__main__': array = [3, 4, 5, -3, 100, 1, 89, 54, 23, 20] n = len(array) tugOfWar(array, n)
OUTPUT :
First subset: 4 100 1 23 20 Second subset: 3 5 -3 89 54
You may also like :
Leave a Reply