Question

In Java, implement a dynamic programming solution to the Set Partition problem.

Recall that the Set Partition problem, given a set S = {a₁, a₂, …, a_n} of positive integers (representing assets) requires partitioning into two subsets S₁ and S₂ that minimizes the difference in the total values of S₁ and S_2.

For testing your code,

a) populate an initial set of 100 assets, with random values between 1 and 1000, identify the (minimum) difference between the two partitions, and time your set-partitioning algorithm.

b) populate again an initial set of 100 assets, but with random values between 1 and 100,000, identify the (minimum) difference between the two partitions, and time your set-partitioning algorithm.

Write and submit the code, along with a Report your findings with the two populations, minimum difference between the partitions, and times. In addition, provide in your report the dynamic programming formula and your reasoning for its correctness.

**Make sure to follow ALL instructions please**

Answer 1

// A Recursive java program to solve 
// minimum set partition problem.
import java.io.*;
import java.util.Random;

class Main {
    // Returns the minimum value of
    // the difference of the two sets.
    static int findMin(int array[], int n) {
        // Calculate total of all elements
        int total = 0;
        for (int i = 0; i < n; i++)
            total += array[i];

        // Create an array to store
        // results of subproblems
        boolean res[][] = new boolean[n + 1][total + 1];

        // Initialize first column as true.
        // 0 total is possible with all elements.
        for (int i = 0; i <= n; i++)
            res[i][0] = true;

        // Initialize top row, except res[0][0],
        // as false. With 0 elements, no other
        // total except 0 is possible
        for (int i = 1; i <= total; i++)
            res[0][i] = false;

        // Fill the partition table
        // in bottom up manner
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= total; j++) {
                // If i'th element is excluded
                res[i][j] = res[i - 1][j];

                // If i'th element is included
                if (array[i - 1] <= j)
                    res[i][j] |= res[i - 1][j - array[i - 1]];
            }
        }

        // Initialize difference of two totals.
        int difference = Integer.MAX_VALUE;

        // Find the largest j such that res[n][j]
        // is true where j loops from total/2 t0 0
        for (int j = total / 2; j >= 0; j--) {
            // Find the
            if (res[n][j] == true) {
                difference = total - 2 * j;
                break;
            }
        }
        return difference;
    }

    // Driver program
    public static void main(String[] args) {
        // create instance of Random class
        Random rand = new Random();
        int ran = 1000; // change the value to change the range of random numbers
        int[] array = new int[100];
        for (int i = 0; i < 100; i++) {
            array[i] = rand.nextInt(ran) + 1;
        }
        int n = array.length;
        long startTime = System.nanoTime();
        System.out.println("The minimum difference between 2 sets of random values between 1 and " + ran + " is "
                + findMin(array, n));
        long endTime = System.nanoTime();
        long duration = (endTime - startTime) / 1000000;
        System.out.println("Time required: " + duration + " milliseconds.");

    }
}

(a) Output when random values between 1 and 1000

The minimum difference between 2 sets of random values between 1 and 1000 is 0
Time required: 58 milliseconds.

(a) Output when random values between 1 and 100000

The minimum difference between 2 sets of random values between 1 and 100000 is 0
Time required: 4217 milliseconds.

Reasoning:

Here we are creating a 2dimensional matrix res[n+1][total+1] where n is the number of elements in the provided set and total is the sum of all these elements. We are here solving in a bottom-up fashion.
We will divide the set into 2 partitions
Let res[n+1][total+1] = {1 if a subset from 1st to i'th has a sum equal to j, 0 otherwise} where i is from 1 to n and j is from 0 to total of all elements.
So, res[n+1][total+1] will be 1 if the sum j is achieved including i'th item or if the sum j is achieved excluding i'th item.

Let sum of all the elements be S.

To find the min difference in the total values of the two set, we will find j so that min{total - j*2 : res[n][j] == 1 } where j changes from 0 to total/2

The idea is, total of S1 is j and it should be closest to sum/2, i.e., 2*j should be closest to the total.