问归纳法证明背包递推返回最优解

EN

要证明该算法的正确性，您可以执行以下三个步骤

1. 证明算法产生了一个可行的列表：

因为算法描述了我们将做出最大的选择，并且我们将始终做出选择，所以我们有一个可行的列表

1. 证明了该算法具有贪婪选择性质：

在这种情况下，我们想要证明我们的算法的第一选择可以是最优解的一部分。

1. 证明了算法有最优子结构:我们可以通过假设形成两个列表来实现：

U(最优列表)和P(我们的算法选择的列表)。我们可以假设这两个列表在某一时刻一定是不同的。设差异点为Uj和Pj (即在索引j之后，P将包含与U不同的对象，U结束于索引j)。因为在P中只选择最大的元素，并且元素的数量与U相同，所以Pj+1将溢出背包，或者我们将使最优解U变得更好，这是不可能的。因此，该问题具有最优子结构。

这样我们就可以证明算法是正确的。

如果一个问题可以分解为子问题，并且你可以使用递归找到子问题的最优解，那么这个问题就有“最优子结构”。你的问题有最优子结构(就像任何DP可解问题一样！)。使用归纳法证明你的程序确实会得到最优解的证据，可以在here找到。