CODEWITHSUNDEEP
pythonalgorithmpython-2.7
govindreddy
govindreddy

Reputation: 21

Evenly distribute int values into two lists whose sums must be nearly equal

I want to evenly distribute int values of a list into two lists whose sums must be nearly equal. If they are not exactly equal, the difference should be returned.

li=[5,8,13,27,14]
first_list=[27,8)
second_list=[14,13,5]
return sum(first_list)-sum(second_list) #3

Upvotes: 1

Views: 1661

Answers (1)

amit
amit

Reputation: 178491

This is the optimization problem for Partition Problem, which is NP-Complete.

There is no known polynomial solution, but there are some heuristics and approximation algorithms.

Also, for relatively small integers, there is a Dynamic Programing solution that might be feasible, or if the input (number of elements) is relatively small - an exponential brute force solution can be used.

Upvotes: 4

Related Questions