Explore
ProGrad Programs
Placement Prep
TCS Codevita
Live Placement Training
Live Aptitude Training
Live Programming Training
Webinars
About Us

Edit
Reply




Edit

Minimum sum partition problem using dynamic programming | FACE Prep

Published on 11 Mar 2020

Minimum sum partition problem using dynamic programming is discussed here. 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.


Program for the minimum sum partition problem


C++

Output
Input - 5 5 7 3 1 9 Output - 1


Test Case 1

I/P

5

5 7 3 1 9

O/P

1


Test Case 2

I/P

4

14 25 78 96

O/P

7


Test Case 3

I/P

7

45 63 52 41 89 75 65

O/P

18


Test Case 4

I/P

6

14 25 78 96 32 10

O/P

13


Test Case 5

I/P

6

2 2 2 2 2 2

O/P

0


Recommended Programs





If you have any feedback about this article and want to improve this, please write to enquiry@faceprep.in
Explore 'c plus plus'
Articles Practice Exercises