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

Question

我想弄清楚如何为可以使用动态规划解决的问题找到最佳路径。我对我们尝试针对 space.

进行优化的情况感兴趣

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

设如下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解决方案，没有做任何space优化如下：

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）。

我使用的逻辑如下：

矩阵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
dp[][] 中的第 4 行（索引 3）对应于第 3 项，因此我将 dp[3][9]（右下角）与 dp[2][9] 进行比较.由于两个值相同，我知道 项目 3 未被选中 。我去dp[2][9].
我比较 dp[2][9] 和 dp[1][9]。由于值不同，我知道 项目 2 被选中 。我转到 dp[1][9 - 项目 2 的重量] => dp[1][4].
我比较dp[1][4]和dp[0][4]。值不同，所以我知道 项目 1 被选中 。我转到 dp[0][4 - 项目 1 的重量] => dp[0][0].
dp[0][0] 是终端状态所以我 return.

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

我的问题是：

当我针对 space 进行优化时，如何找到路径（在本例中为选择的项目）？有可能吗？

例如，我可以不使用矩阵，而是使用 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 或 shortest-path），将路径记住为 reverse-order 链表效果很好。这些列表共享尾巴，通常您必须记住的列表具有相似的历史。每隔一段时间，您可能需要扫描结构以确保它仍然紧凑。当您确实需要时，您可以删除每第 N 个元素，这将要求您在重建路径时进行小型搜索以连接每一对。

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

Most optimal path in a dynamic programming problem

algorithm

mathematical-optimization

dynamic-programming