Minimum sum partition problem using dynamic programming | faceprep

Minimum sum partition problem using dynamic programming | faceprep

The minimum sum partition problem using dynamic programming is discussed here.

Minimum sum partition problem using dynamic programming


Given a set of integers, partition the set such the difference between the two set is minimum (absolute difference ) and print the difference:

Sample Input:

4 (number of elements of the array)

14 25 78 96 (array elements)

Sample Output:

7

Explanation:

S1 = {96, 14}

S2 = {78, 25}

Sum of S1 = 110

Sum of S2 = 103

|S1 – S2| = 7


Algorithm for the minimum sum partition problem

  • Divide the set into two parts.
  • Consider the following factors while partitioning it.
  • Let dp[n+1][sum+1] = {1 if some subset from 1st to i’th has a sum equal to j 0 otherwise}
  • Repeat from i = 1 to n
  • Repeat from j = 1 to sum of all elements
  • So, dp[n+1][sum+1] will be 1 if
  • Sum j is achieved including the i’th item
  • Sum j is achieved excluding the i’th item.
  • Let the sum of all the elements be S.
  • To find Minimum sum difference, w have to find j such that Min {sum – j*2 : dp[n][j] == 1 } where j varies from 0 to sum/2
  • The idea is, the sum of S1 is j and it should be closest to sum/2, i.e., 2*j should be closest to sum.


face prep pro ad bannerClick here to learn more about FACE Prep PRO


Program for the minimum sum partition problem

@@coding::1@@


Recommended Programs


Minimum sum partition problem using dynamic programming

c