java - 坚持对 DP 算法进行微调(考虑决胜局)

Question

示例输入:

45 8 4 10 44 43 12 9 8 2

第一个数字 = N

第二个数字 = T

后面的 T 个数字 = 一组值

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

2 8 9 12 10 4 sum:45

我的问题是，在决胜局之间我没有要决定的事情。打破平局的因素将是具有更多元素的集合。所以我的程序打印了这个:

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 二维数组走在正确的轨道上。但是您不应该将累积成本跟踪为每个单元格的值，该值已经由第二个索引(在您的情况下为 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 }

从这个表中，您知道可以用来求和为 5 的最大元素数是 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 来构造您的结果集。