algorithm - 背包算法 : Why we use wt[i-1] instead of 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

如果我们不选择第 i 项，这会给出我们可以获得的最佳值。考虑项目(值(value)，数量)； (2,1)、(3,2)、(4,5) 和一个体积为 5 的袋子。

当我们处理第三个项目时，我们可以得到一个值为 4 的值。但是如果我们不接受它，我们可以得到我们之前的最大值 5。Check this video.