shubhinanugullu's blog

Partition an even sized multi-set of whole numbers into two multi-sets of equal size having almost equal sums

By shubhinanugullu, history, 10 years ago, In English

We are given a multi-set of whole numbers S of size 2n. All whole numbers in S are in the range [0, d]. We need to partition S into two multi-sets A and B such that |A| = |B| = n. Our task is to find such A and B which minimise |sum(A)-sum(B)|. What is an efficient algorithm to do so?

  • Vote: I like it
  • +5
  • Vote: I do not like it

Comments Comments (8)
| Write comment?
»
10 years ago, hide # |
 
Vote: I like it +6 Vote: I do not like it

Do you have a link to the original statement?

→ Reply
»
10 years ago, hide # |
← Rev. 2  
Vote: I like it +2 Vote: I do not like it

EDIT:The previous solution was mistaken.

This is standard Knapsack DP. Note that the maximum sum for one possible part is d*n. Now you can perform the standard knapsack, with dp[i][j] denoting whether it is possible to make a sum i using j elements. The transition will be as follows: 

dp[i][j]=dp[i][j-1]|dp[i-a[i]][j-1]

Then we can check for all W whether dp[W][n] is true and find the answer appropriately. As mentioned below,this can be sped up by a factor of 32 using bitsets.

Complexity:O(dn^2)

→ Reply
  • »
    »
    10 years ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it 0 Vote: I do not like it

    But how do I take care of the fact that there should be exactly n elements in both the partitions?

    → Reply
    • »
      »
      »
      10 years ago, hide # ^ |
      ← Rev. 4  
      Vote: I like it -15 Vote: I do not like it

      Edit : Wrong approach

      → Reply
      • »
        »
        »
        »
        10 years ago, hide # ^ |
        ← Rev. 2  
        Vote: I like it +8 Vote: I do not like it

        Suppose your greedy approach is right. Then you could solve the problem of finding the optimal sum difference partition in linear time, just by adding 0s until you double your array size. And this sounds implausible to me.

        What about this test case? 9 6 5 5 5 0

        → Reply
        • »
          »
          »
          »
          »
          10 years ago, hide # ^ |
           
          Vote: I like it 0 Vote: I do not like it

          Oh I see. My greedy approach is incorrect I guess. Thank you for giving the cases.

          Any suggestion then? Would like to know the correct approach too.

          → Reply
          • »
            »
            »
            »
            »
            »
            10 years ago, hide # ^ |
             
            Vote: I like it +8 Vote: I do not like it

            Judging by the observation that the problem with no constraints on the size of the subsets reduces to this one in linear time, I don't think we would find any solutions better than O(n * s) with factor 1 / 32 (or some other complexities that can solve the easier problem, which I do not know :) ).

            There is a rather obvious solution in O(n2 * s / 32) with DP though. Maybe that suffices.

            → Reply
»
10 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

https://en.wikipedia.org/wiki/Partition_problem

→ Reply