坚持对DP算法进行微调（对于仲裁者而言）

Question

样本输入：

45 8 4 10 44 43 12 9 8 2

第一个数字= N.

第二个数字= T.

以下T number =一组值

我的工作是找到所有子集中总和最高的子集，不超过N.打印该集合和总和。因此，该输入的输出将是：

2 8 9 12 10 4 sum:45

我的问题是，我在tiebreakers之间没有什么决定权。决胜因素是具有更多元素的集合。所以我的程序打印出来：

2 43 sum:45 

这是代码（标准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

使用T x N 2维阵列，您处于正确的轨道上。但是你不应该追踪累积成本作为每个单元格的值，这已经被第二个索引（在你的情况下为j）跟踪。相反，跟踪到目前为止您可以求和的最大元素数量。通过这样做，您甚至不需要路径数组。

想象一下N = 5，T = 4的情况，数字为{4,1,1,3}。第一列将跟踪行j == 4中的1和其他位置的0。第二列将跟踪行j == 5中的2，行j == 4和j == 1中的1和其他地方的0。你可以填写这样的东西（可能需要一些调整......）：

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]);
    }
}

最后的dp表看起来像这样：

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 }

从这个表中，你知道你可以用来求和的最大元素数是3.要找出这些元素是什么，从dp[3][5]向后工作。从dp[2][5] != dp[3][5]开始，你必须添加cost[3]（3）作为你的第三个元素，所以将3添加到你的结果集中。要检查的下一个值是dp[2][5 - cost[3]]，或dp[2][2]。将它与左边的单元格进行比较，dp[1][2]。它们不相等，所以你必须添加cost[2]（如果它们相等，那意味着你没有添加cost[2]，下一个要检查的单元格将是dp[1][2]）。继续，直到dp[i][j] == 0或i == 0构建您的结果集。