So a few days ago I was pondering the concept of Dynamic Programming (DynP), trying to grasp it. I read some about it and found some puzzles fit for it. And today I tackled one of those on the dropbox website. Namely, the Subset Sum problem.

The subset sum problem is about finding one, if any, subsets of a given set of digits where the sum is zero (or any other wanted number). For example:

Input:
-6, -9, -10, -11, -15, 1, 2, 3, 4, -3
Output:
-6, 1, 2, 3

As most of you can see, 3 and -3 make up the optimal solution, but that's uninteresting in the general case of the problem.

So one way to tackle this is creating every possible subset and checking their sums, but this requires O(2^n) operations in the worst case.

The other, DynP, way of doing it would be to create a matrix of sums. Where the rows display possible numbers, and the columns display the sum. A little like this:

    | -4 -3 -2 -1  0  1  2  3
  3 |  F  F  F  F  F  F  F  T
 -4 |  T  F  F  T  F  F  F  T
  1 |  T  T  F  T  T  T  F  T

An F in a square says that it's not possible to create this sum (column label) using the values available (current row label, plus every one above it). We see that with the number 3 at our disposal, we can only create the sum 3. When we check the number -4, we need only to look at the row directly above us. Those there marked with a T, plus our current number can make out more combinations. 3 and -4 can create not only 3, but also the sums -1 and -4 (by not using the 3).

With no further ado, I present to you my solution:

import java.util.Arrays;

/***
 * DynP solution to the Subset Sum Problem. 
 * 
 * @author Mikael Silvén
 */
public class PseudoDynamicSmart {
    public static void main(String[] args) {
        int[] solution = solveSubsetSumProblem(generatePseudoRandomList(50), 0);
        System.out.println();
        if (solution != null) {
            int sum = 0;
            System.out.println("solution:");
            for (int i : solution) {
                sum += i;
                System.out.print(i + " ");
            }
            System.out.println("= " + sum);

        } else {
            System.out.println("no solution");
        }
    }

    public static int[] solveSubsetSumProblem(int[] bigset, int wanted) {
        System.out.print("[ ");
        for (int i : bigset)
            System.out.format(i + " ");
        System.out.println("]");

        // Since we dont know the bounds, we calculate them
        int upperbound = 0;
        int lowerbound = 0;
        for(int i : bigset)
        {
            if(i > upperbound)
                upperbound = i;
            if(i < lowerbound)
                lowerbound = i;
        }
        
        // Convinience variables.
        int lb = Math.abs(lowerbound);
        int width = Math.abs(upperbound - lowerbound);
        
        // The matrixes used to keep track of stuff.s
        boolean[][] M = new boolean[bigset.length][width + 1];
        int[][] sums = new int[bigset.length][width + 1];

        // Fill the matrix, using n * width operations.
        M[0][lb + bigset[0]] = true;
        sums[0][lb + bigset[0]] = bigset[0];
        for (int row = 1; row < bigset.length; row++) {
            int x = bigset[row];
            for (int subsum = 0; subsum <= width; subsum++) {
                if (M[row - 1][subsum]) {
                    M[row][subsum] = true;
                    sums[row][subsum] = sums[row - 1][subsum];
                }

                int sum = sums[row - 1][subsum] + x;
                if (sum >= lowerbound && sum <= upperbound) {
                    M[row][lb + sum] = true;
                    sums[row][lb + sum] = sum;
                }
            }
        }

        plotMatrix(M, bigset, lowerbound, upperbound);

        int[] answer = new int[bigset.length];
        int numans = 0;
        int wantedcol = lb + wanted;
        for (int row = bigset.length - 1; row >= 0; row--) {
            if (M[row][wantedcol]) {
                try {
                    if (M[row - 1][wantedcol]) {
                        continue;
                    }
                } catch (ArrayIndexOutOfBoundsException e) {
                    // This happens when we're on the last row
                }
                int number = bigset[row];
                answer[numans++] = number;
                wantedcol -= number;
            }
        }
        if(numans > 0)
            return Arrays.copyOf(answer, numans);
        return null;
    }

    private static void plotMatrix(boolean[][] m, int[] unsorted, int lower, int upper) {

        int len = Math.max((lower+"").length(),
                (upper+ "").length());
        String fString = "%1$" + (len + 1) + "s";

        System.out.format(fString, " ");
        System.out.print(" |");
        for (int i = lower; i <= upper; i++) {
            System.out.format(fString, i);
        }
        System.out.println();

        int width = Math.abs(upper - lower);
        for (int row = 0; row < unsorted.length; row++) {
            System.out.format(fString, unsorted[row]);
            System.out.print(" |");
            for (int col = 0; col <= width; col++) {
                System.out.format(fString, m[row][col] ? "T" : "F");
            }
            System.out.println();
        }

    }

    private static int[] generatePseudoRandomList(int size) {

        // int[] list = { -6, -9, -10, -11, -15, 1, 2, 3, 4, -3 };
        int multiplier = 5;
        int[] list = new int[size];
        for (int i = 0; i < size; i++) {
            int rnd = 0;
            do {
                rnd = -(multiplier * size)
                    + (int) (2 * multiplier * size * (Math.random()));
            } while (unfitNumber(list, rnd));
            list_ = rnd;
        }

        return list;
    }

    /***
    * An unfit number x, is a number where |x| is already in the given list, or zero
    */
    private static boolean unfitNumber(int[] list, int rnd) {
        if (rnd == 0)
            return true;
        for (int i = 0; i < list.length; i++) {
            if (list_ == rnd || list_ == -rnd)
                return true;
        }
        return false;
    }
}

This does not exactly match the Dropbox version of the problem, but it's just a matter of adding a HashMap (or equivalent), using the strings as values and costs as keys.

This version can be optimised further by simply breaking whenever the wanted sum is achieved.

It's called Pseudo because that's just what it is. It's not 2^n exponential, but not truly polynomial either. Since the width depends on the numbers in the input.

There will definitely be more DynP stuff coming, together with more puzzles. This is fun :)