Implement the solution to the Minimum Partition problem using dynamic programming.?

The Minimum Partition problem is a classic dynamic programming problem, where we are given an array of integers and we are asked to divide the array into two subsets such that the difference of the sum of the two subsets is minimized.

Let’s assume that the input array is of length N and the sum of all elements in the array is sum. We need to find two subsets of the array S1 and S2 such that the absolute difference between the sum of S1 and the sum of S2 is minimized.

To solve this problem using dynamic programming, we can use a two-dimensional boolean matrix dp. The matrix dp[i][j] will be true if the sum j can be achieved using elements up to the i-th index in the input array.

The approach to filling this matrix is to start with the base case dp[0][0]=true (an empty set has a sum of zero) and dp[0][j]=false (cannot achieve any sum with an empty set, except zero), then for each element in the input array, we will either select it or not select it.

If the j-th value is less than or equal to the i-th element, we can either select it or not select it. If the j-th value is greater than the i-th element, we can not include i-th element in any subset if j-th value is less than i-th element.

So we fill the matrix as following:

  dp[0][0] = true; 
  for (int i = 1; i <= N; i++) {
      for (int j = 0; j <= sum/2; j++) {
          dp[i][j] = dp[i-1][j]; 
          if (j >= arr[i-1]) {
              dp[i][j] |= dp[i-1][j-arr[i-1]];
          }
      }
  }

Once we have calculated the dp matrix, the minimum difference between partition can be calculated by finding the largest value of j such that dp[N][j] is true. We can then calculate the difference between sum-j and j to find the minimum difference between the two subsets.

Here’s the complete Java code implementation of the above algorithm:

public class MinimumPartition {

    public static int findMinimumPartition(int[] arr) {
        int N = arr.length;
        int sum = Arrays.stream(arr).sum();
        boolean[][] dp = new boolean[N+1][sum/2+1];

        // base cases
        dp[0][0] = true; 
        for (int i = 1; i <= N; i++) {
            dp[i][0] = true; 
        }

        // fill the dp matrix
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= sum/2; j++) {
                dp[i][j] = dp[i-1][j];
                if (j >= arr[i-1]) {
                    dp[i][j] |= dp[i-1][j-arr[i-1]];
                }
            }
        }

        // find the largest value of j such that dp[N][j] is true
        int j = sum/2;
        while (j >= 0 && !dp[N][j]) {
            j--;
        }

        // return the minimum difference
        return sum - 2*j;
    }

    public static void main(String[] args) {
        int[] arr = {1,6,11,5};
        int minDiff = findMinimumPartition(arr);
        System.out.println("The minimum difference between the two subsets is: " + minDiff);
    }
}

The output of the above code will be:

The minimum difference between the two subsets is: 1

In this example, the two subsets of the input array are 1,5 and 6,11. The difference between their sum is minimized to 1.