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...

Candis

Show what you have so that others can comment on where you went wrong. – Botanical

ok I'm now editing. However, I'm looking different and correct algorithm – Candis

Did you look at #890671 ? – Bouncy

I searched but I didn't find this question in SO. thanks – Candis

Whoops, I voted to close as exact dupe and now see that the question Michael suggested (while still highly relevant) has the additional constraint that the 2 lists be equal-sized. – Scheel

Answer 1

The problem is NPC, but there is a pseudo polynomial algorithm for it, this is a 2-Partition problem, you can follow the way of pseudo polynomial time algorithm for sub set sum problem to solve this. If the input size is related polynomially to input values, then this can be done in polynomial time.

In your case (weights < 250) it's polynomial (because weight <= 250 n => sums <= 250 n^2).

Let Sum = sum of weights, we have to create two dimensional array A, then construct A, Column by Column

A[i,j] = true if (j == weight[i] or j - weight[i] = weight[k] (k is in list)).

The creation of array with this algorithm takes O(n^2 * sum/2).

At last we should find most valuable column which has true value.

Here is an example:

items:{0,1,2,3} weights:{4,7,2,8} => sum = 21 sum/2 = 10

items/weights 0|  1  | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10    
  --------------------------------------------------------- 
  |0             |  0  | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0
  |1             |  0  | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0
  |2             |  0  | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1
  |3             |  0  | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1

So because a[10, 2] == true the partition is 10, 11

This is an algorithm I found here and edited a little bit to solve your problem:

bool partition( vector< int > C ) {
 // compute the total sum
 int n = C.size();
 int N = 0;
 for( int i = 0; i < n; i++ ) N += C[i];
 // initialize the table 
 T[0] = true;
 for( int i = 1; i <= N; i++ ) T[i] = false;
 // process the numbers one by one
 for( int i = 0; i < n; i++ )
  for( int j = N - C[i]; j >= 0; j--)
   if( T[j] ) T[j + C[i]] = true;

 for(int i = N/2;i>=0;i--)
    if (T[i])
      return i;
 return 0;
}

I just returned first T[i] which is true instead of returning T[N/2] (in max to min order).

Finding the path which gives this value is not hard.

Soundless

Answer 2

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.

Declivitous

knapsack is "NPC-Strong" problem but this problem is just NPC (It' not strong), If you reformulate this as KNapsack you will create harder problem, It's like reformulate P problem to NPC problem (not exactly but it's like this). – Soundless

@Saeed: For the special case where all weights are non-negative, the knapsack problem is not NPC strong. – Declivitous

yes, So edit your first sentence, this problem is exactly known problem (2-Partition), and any reformulation may be causes ambiguity (like this) unless all things explain well. for example, Mark Byers, offered brute force which is wrong in this case when it can be done in polynomial time.(IMHO you made no mistake but may be causes to others mistakes). – Soundless

@Saeed: You may have a point. On the other hand, partition problem (as you may know) is just a special case of the more well-known knapsack problem. So which attack path to take is largely a matter of taste. Personally I think it is easier to try to derive from the most general well-known problem possible. – Declivitous

IMO NO, partition is NOT a special case of KNapsak (I didn't know where you read this or how do you think), may be "2-Partition" is "KNapsak with non negative weights", but general partition is very different, for example 3-Partition is a (first) problem to showing it's NPC-Strong and from this showing that 4-Partition is NPC Strong and from that showing 3-Dimensional Matching is Strong(now we have hierarchy of proof), and if you wanna say that X is special case of Y I can say it in reverse, but as I said If there is no good clarification, will be causes to ambiguity. – Soundless

This solution is very neat. This helped me a lot. Thanks. – Carlist

Answer 3

This problem is at least as hard as the NP-complete problem subset sum. Your algorithm is a greedy algorithm. This type of algorithm is fast, and can generate an approximate solution quickly but it cannot find the exact solution to an NP-complete problem.

A brute force approach is probably the simplest way to solve your problem, although it is will be to slow if there are too many elements.

• Try every possible way of partitioning the elements into two sets and calculate the absolute difference in the sums.
• Choose the partition for which the absolute difference is minimal.

Generating all the partitions can be done by considering the binary representation of each integer from 0 to 2^n, where each binary digit determines whether the correspending element is in the left or right partition.

Novelistic

brute force is not the answer in most algorithmic problems because the time is important. 2) Subset sum solution sounds good. I'll search it – Candis

Please observe: In the case where all weights are non-negative, this problem is only weakly NP-complete, and has polynomial time solutions. Brute force is not a good idea. – Declivitous

@hilal: You are right, it's not the optimal algorithm. I thought you were trying to find a correct algorithm. The knapsack approach suggested by kotlinski looks good. :) – Novelistic

Answer 4

Trying to resolve the same problem I have faced into the following idea which seems too much a solution, but it works in a linear time. Could one provide an example which would show that it does not work or explain why it is not a solution?

arr = [20,10,15,6,1,17,3,9,10,2,19] # a list of numbers

g1 = []
g2 = []

for el in reversed(sorted(arr)):
    if sum(g1) > sum(g2):
        g2.append(el)
    else:
        g1.append(el)

print(f"{sum(g1)}: {g1}")
print(f"{sum(g2)}: {g2}")

Dredge

This greedy algorithm doesn't always work. Try 10 9 8 7 4 for example. – Gondolier

Answer 5

Typescript code:

import * as _ from 'lodash'
function partitionArray(numbers: number[]): {
    arr1: number[]
    arr2: number[]
    difference: number
} {
    let sortedArr: number[] = _.chain(numbers).without(0).sortBy((x) => x).value().reverse()
    let arr1: number[] = []
    let arr2: number[] = []
    let median = _.sum(sortedArr) / 2
    let sum = 0

    _.each(sortedArr, (n) => {
        let ns = sum + n
        if (ns > median) {
            arr1.push(n)
        } else {
            sum += n
            arr2.push(n)
        }
    })
    return {
        arr1: arr1,
        arr2: arr2,
        difference: Math.abs(_.sum(arr1) - _.sum(arr2))
    }
}

Blanchard