Minimum sum partition problem using dynamic programming | faceprep

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
  1. Sum j is achieved including the i’th item
  2. 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 is given below.

/* C++ program for the minimum sum partition problem */

#include<bits/stdc++.h>
using namespace std;
int main()
{
   int n;
   cin>>n;
   int a[n],sum=0;
   for(int i=0;i<n;i++)
   {
       cin>>a[i];
       sum+=a[i];
   }
   bool dp[n+1][sum/2+1];
   for(int i=0;i<=n;i++)
       dp[i][0]=true;
   for(int i=0;i<=sum/2;i++)
       dp[0][i]=false;
   for(int i=1;i<=n;i++)
   {
       for(int j=1;j<=sum/2;j++)
       {
           dp[i][j]=dp[i-1][j];
           if(j >= a[i-1])
               dp[i][j] |= dp[i-1][j-a[i-1]];
       }
   }
   int diff=INT_MAX;
   for(int i=sum/2;i>=0;i–)
   {
       if(dp[n][i])
       {
           diff=sum-2*i;
           break;
       }
   }
   cout<<diff;
}

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