背包算法：为什么我们使用 wt[i-1] 而不是 wt[i]

Question

考虑背包算法实现的以下部分：

 // Build table K[][] in bottom up manner
for (i = 0; i <= n; i++)
{
    for (w = 0; w <= W; w++)
    {
        if (i == 0 || w == 0)
            K[i][w] = 0;
        else if (wt[i - 1] <= w)
            K[i][w]
                    = max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w]);
        else
            K[i][w] = K[i - 1][w];
    }
}

我有一个基本的疑问，为什么我们在检查第 i 个元素时使用 wt[i-1]？

Answer 1

您的第一个 for 循环运行s i=0; i<=n; i++ 这意味着它将运行 n+1 次迭代，而您只有 n 个对象。这没关系，因为 i=0 是分配 K[i][w] = 0 的特殊情况，所以基本上这会将第一行初始化为 0。现在i=0有特殊意义，数组平移1（所以i=1指的是权重为wt[0]的第一个对象，以此类推）。

你真的不需要这种技巧，但它们在动态规划中很常见。如果你不想为 0 添加一个额外的列，你可以省略它，但是你需要添加一堆检查以确保你不会尝试访问分配区域之外的内存，这有点更难测试，因为您的逻辑有两条路径。

Answer 2

这给了我们如果不 select 项目 i 可以获得的最佳价值。考虑项目（价值，数量）； (2,1)、(3,2)、(4,5) 和一袋体积 5。

当我们处理第三项时，我们可以取值为 4。但是如果我们不取它，我们可以使用之前的最大值 5。Check this video.

背包算法：为什么我们使用 wt[i-1] 而不是 wt[i]

Knapsack Algorithm: Why we use wt[i-1] instead of wt[i]

algorithm

knapsack-problem

dynamic-programming