CSES 电梯乘坐解决方案为何有效？

Question

大家！当我解决 cses.fi 的问题时，我遇到了一个我完全无法理解的问题。我在互联网上搜索并找到了 DP 子集的解决方案，但仍然无法意识到它为什么有效。下面是问题及其解决方案... https://cses.fi/problemset/task/1653 https://cses.fi/book/book.pdf（第 103 - 104 页）

简而言之，作者提供了对每个子集进行计数的值：所需的最小乘车次数（“rides(S)”）以及对于该数量的乘客，最后一组人的最小体重（“last(S)”） '）。如果我们考虑某个集合S，那么我们需要取出它的一些元素p，从S中提取它，重新计算所需的值rides(S\p)和last(S\p)，尝试将元素p添加到具有权重的最小组中如果可能的话，最后（S \ p），否则为 p 创建一个新组。然后我们需要对集合 S 中所有可能的 p 重复该算法，并取最小可能对 {rides(S\p);last(S\p)}。

请告诉我为什么我们在我描述的算法中得到所需的 S 值。我不明白为什么它会经历所有可能的选项，为什么它是详尽无遗的。

我试图证明它的准确性，但我数学不太好。

Answer 1

我将与您分享如何通过启发式方式证明这一点。

如果有神的话...

如果你有n个人，有一个大神可以告诉你所有

n - 1

人的可能性的最小行程以及最后一组的最小总重量。

通过检查每一个n-1人的案例，我们可以得到n人的正确答案。你可以通过反证法证明这一点：如果有一个不包含在内的正确答案，那就意味着：

1. 上帝是错的，这与我们的定义相矛盾（上帝总是对的）
2. 大神是对的，但是正确答案并不包含在这样的情况下。这是错误的，因为对于最小乘车方案来说，前

   n - 1

   人的安排已经包含在上帝的答案中了，我们检查了最后一个人的所有可能性，所以它是包含的。

如果没有神...

现在你需要计算一下神之前为你提供了什么。所有

n - 1

人可能性的答案。

想想还有更少的力量神可以告诉你所有

n - 2

人可能性的答案。在弱神帮助下，我们可以用同样的方法计算出

n - 1

人可能性的答案。

然后能解决

n - 2

的力量较小的神就消失了，你只能在

n - 3

上找到帮助你的神。 De javu.

神一路消失，只剩下1个人。好吧，我们需要一个神来解决只有 1 个人的问题吗？我们可以自己做到这一点：对于每个人，我们需要 1 次骑行，最后一组的最小重量就是该人的体重。

综上所述，可以证明该解是正确的。