algorithm - 动态规划问题中的最优路径

Question

我正在尝试找出如何为可以使用动态规划解决的问题找到最佳路径。我对我们尝试优化空间的情况很感兴趣。

为了更好地解释我的问题，让我们考虑一下背包问题。

---

设如下3项:

        I1      I2      I3
---------------------------
Val     5       4       3     

Weight  4       5       2

这里的最优路径是应该为最优解选择的项目。

递归关系如下:

Let n be the nth item 
let c be the remaining capacity in the knapsack

f(n, c) = 0             // if n=0
f(n, c) = f(n-1, c)     // if weight[n] > c
f(n, c) = max(f(n-1, c), value[n] + f(n-1, c-weight[n]))  // if weight[n] <= c

我已经基于这个递归关系(在java中)写了一个DP解决方案，没有做任何空间优化如下:

public static void main(String[] args) {
    int[] value = {5, 4, 3};
    int[] weight = {4, 5, 2};

    int capacity = 9;


    int[][] dp = new int[value.length+1][capacity+1];

    for(int i=0; i<=value.length; i++) {
        for(int j=0; j<=capacity; j++) {
            if(i==0) {
                dp[i][j] = 0;
            } else {
                if(weight[i-1] <= j){
                    dp[i][j] = Math.max(dp[i-1][j], value[i-1] + dp[i-1][j - weight[i-1] ]);
                } else {
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
    }

    System.out.println("optimal value is: " + dp[value.length][capacity]);
}

这会打印出最优解 9。

我现在想找出哪些项目构成了最佳解决方案(在本例中为 I1、I2)。

我使用的逻辑如下:

1. 矩阵dp[][]如下:

   0 0 0 0 0 0 0 0 0 0
   0 0 0 0 5 5 5 5 5 5
   0 0 0 0 5 5 5 5 5 9
   0 0 3 3 5 5 8 8 8 9

2. dp[][] 中的第 4 行(索引 3)对应于项目 3，因此我将 dp[3][9](右下角)与 dp[2][9] 进行比较。由于两个值相同，我知道未选择第 3 项。我去 dp[2][9]。

3. 我比较 dp[2][9] 和 dp[1][9]。由于值不同，我知道选择了第 2 项。我转到 dp[1][9 - 项目 2 的重量] => dp[1][4]。
4. 我比较 dp[1][4] 和 dp[0][4]。值不同，所以我知道选择了第 1 项。我转到 dp[0][4 - 项目 1 的重量] => dp[0][0]。
5. dp[0][0] 是终端状态，所以我返回。

这个操作的结果是:[1, 1, 0] 其中 1 表示 item1，item2 被拿走了，0 表示 item3 没有被拿走。

---

我的问题是:

优化空间时如何找到路径(在本例中为挑选的项目)？有可能吗？

例如，我可以不使用矩阵，而是使用 2 个数组并按如下方式更改程序:

public static void main(String[] args) {
    int[] value = {5, 4, 3};
    int[] weight = {4, 5, 2};

    int capacity = 9;

    int[] row0 = new int[capacity+1];
    int[] row1 = new int[capacity+1];
    for(int i=0; i<=3; i++) {
        for(int j=0; j<=capacity; j++) {
            if(i==0) {
                row1[j] = 0;
            } else {
                if(weight[i-1] <= j) {
                    row1[j] = Math.max(row0[j], value[i-1]+ row0[j-weight[i-1]]);
                } else {
                    row1[j] = row0[j];
                }
            }
        }
        for(int j = 0; j< row0.length; j++)
            row0[j] = row1[j];
    }

    System.out.println("optimal value is: " + row1[capacity]);

}

如果我这样做，我最多只有最后两行:

row0 = { 0 0 0 0 5 5 5 5 5 9 }
row1 = { 0 0 3 3 5 5 8 8 8 9 }

仅此信息如何追溯路径？

Answer 1

没有一个好的解决方案可以解决所有的 DP 问题。

例如，对于这个问题，我会为每个可访问的总和保留一个位掩码，以指示您选择了哪些元素来生成该总和。这适用于背包，因为元素的数量很少，选择顺序无关紧要。

对于许多其他 DP 问题(例如 LCS 或最短路径)，将路径记住为倒序链表会很有效。这些列表共享尾部，通常您必须记住的列表具有相似的历史。每隔一段时间，您可能需要扫描结构以确保它仍然紧凑。当您确实需要时，您可以删除每第 N 个元素，这将要求您在重建路径时进行小型搜索以连接每一对。