Stuck on making a slight adjustment to a DP algorithm (account for tiebreaker)

Question

Sample input:

45 8 4 10 44 43 12 9 8 2

First number = N

Second number = T

Following T numbers = A set of values

My job is to find the subset where the sum is the highest possible one out of all subsets, that doesn't exceed N. Print that set, and the sum. So, output for that input would be:

2 8 9 12 10 4 sum:45

My issue is, I don't have something to decide between tiebreakers. The tiebreaking factor would be the set with larger amount of elements. So my program prints this:

2 43 sum:45 

Here is the code (standard I/O):

        int val = reader.nextInt();
        int num = reader.nextInt(); // never exceeds 20
        int[] cost = new int[20]; 
        int[][] dp = new int[10000][10000]; 
        int[][] path = new int[10000][10000];
        for (int i = 0; i < num; i++) {
            cost[i] = reader.nextInt();
        }
        for (int i = 0; i < num; i++) {
            for (int j = 0; j <= val; j++) {
                if (j < cost[i]) {
                    dp[i + 1][j] = dp[i][j];
                }
                else {
                    if (dp[i][j] < dp[i][j - cost[i]] + cost[i]) {
                        path[i+1][j] = 1;
                        dp[i + 1][j] = dp[i][j - cost[i]] + cost[i];
                    }
                    else {
                        dp[i + 1][j] = dp[i][j];
                    }
                }
            }
        }
        int k = val;
        for (int i = num; i >= 1; i--) {
            if (path[i][k] == 1 && k >= 0) {
                System.out.print(cost[i - 1] + " ");
                k = k - cost[i - 1];
            }
        }
        System.out.print("sum:" + dp[num][val] + '\n');

Answer 1

You are on the right track with your T x N 2-dimensional array. But you shouldn't be tracking the accumulated cost as the value of each cell, that is already tracked by the 2nd index (j in your case). Instead, track the maximum number of elements you can sum to get to that cost so far. By doing this, you don't even need a path array.

Imagine a scenario where N = 5, T = 4, and the numbers are {4, 1, 1, 3}. The first column would track a 1 in the row j == 4 and 0 everywhere else. The second column would track a 2 in the row j == 5, a 1 in rows j == 4 and j == 1 and 0 everywhere else. You could fill it with something like this (may need some tweaking...):

dp[0][cost[0]] = 1;
for (int i = 1; i < T; i++) {

    dp[i][cost[i]] = 1;

    for (int j = N - 1; j >= 0; j--) {
        if (j >= cost[i] && dp[i-1][j-cost[i]] > 0) {
            dp[i][j] = dp[i-1][j-cost[i]] + 1;
        }
        dp[i][j] = Math.max(dp[i][j], dp[i-1][j]);
    }
}

The dp table at the end would look like this:

Sum (j)
     5 |    0    2    2    3
     4 |    1    1    1    2
     3 |    0    0    0    1
     2 |    0    0    2    2
     1 |    0    1    1    1
     0 |    0    0    0    0
______________________________
  cost |  { 4    1    1    3 }

From this table, you know that the maximum number of elements you can use to sum to 5 is 3. To find out what those elements are, work backwards from dp[3][5]. Since dp[2][5] != dp[3][5], you must have added cost[3] (3) as your third element, so add 3 to your result set. The next value to inspect is dp[2][5 - cost[3]], or dp[2][2]. Compare that to the cell to the left, dp[1][2]. They aren't equal, so you must have added cost[2] as well (if they were equal, that means you didn't add cost[2], and the next cell to inspect would be dp[1][2]). Continue until dp[i][j] == 0 or i == 0 to construct your result set.