algorithm - divide list in two parts that their sum closest to each other

Question

This is a hard algorithms problem that :

Divide the list in 2 parts (sum) that their sum closest to (most) each other

list length is 1 <= n <= 100 and their(numbers) weights 1<=w<=250 given in the question.

For example : 23 65 134 32 95 123 34

1.sum = 256

2.sum = 250

1.list = 1 2 3 7

2.list = 4 5 6

I have an algorithm but it didn't work for all inputs.

1. init. lists list1 = [], list2 = []
2. Sort elements (given list) [23 32 34 65 95 123 134]
3. pop last one (max one)
4. insert to the list which differs less

Implementation : list1 = [], list2 = []

1. select 134 insert list1. list1 = [134]
2. select 123 insert list2. because if you insert to the list1 the difference getting bigger
   3. select 95 and insert list2 . because sum(list2) + 95 - sum(list1) is less.

and so on...

Answer 1

You can reformulate this as the knapsack problem.

You have a list of items with total weight M that should be fitted into a bin that can hold maximum weight M/2. The items packed in the bin should weigh as much as possible, but not more than the bin holds.

For the case where all weights are non-negative, this problem is only weakly NP-complete and has polynomial time solutions.

A description of dynamic programming solutions for this problem can be found on Wikipedia.