Problem take from ACM and is a variant of the Balanced Partition Problem

**Tug of War**

A tug of war is to be arranged at the local office picnic. For the tug of war, the picnickers must be divided into two teams. Each person must be on one team or the other; the number of people on the two teams must not differ by more than 1; the total weight of the people on each team should be as nearly equal as possible.

Sample Input

100

90

200

Sample Output

190 200

CODE:

import math
import random
n=5
arr = [100,100,100,90,200]
total=indexA=indexB=i=j=sideA=sideB=0
for p in range(0,n):
total = total+arr[p]
split=n/2
a = b = [0]*n
arr.sort()
while indexA< split :
indexA = indexA+1
a[indexA] = arr[i]
if(indexA< split):
indexA=indexA+1
a[indexA] = arr[n-i-1]
sideA = sideA+arr[n-i-1]
sideA =sideA+arr[i]
i=i+1
j=i
while indexB < n-split :
indexB=indexB+1
b[indexB] = arr[j]
sideB = sideB+arr[j]
j=j+1
t1 = split - 1
t2 = split
sideA = sideA + (b[t2]-a[t1])
sideB = sideB + (a[t1]-b[t2])
if split%2 == 0 :
print "side A has total of:", sideA
print "side B has total of:", sideB
else:
sideA = min(sideA, sideB)
sideB= max(sideA, sideB)
print "side A has total of:", sideA
print "side B has total of:", sideB

OUTPUT:

$ python tug.py

side A has total of: 290

side B has total of: 300

For

n=4

arr = [100,100,90,200]

$ python tug.py

side A has total of: 290

side B has total of: 200

For

n=3

arr = [100,90,200]

$ python tug.py

side A has total of: 190

side B has total of: 200

Thanks for Reading!

### Like this:

Like Loading...

*Related*

Isn’t this a greedy approach? If so, are you sure it gives optimal output always?

yes its greedy and does not give the correct solution every time, Need a better solution for this