算法：确定最大乐趣

Question

问题本身可以在这里找到。问题的主要内容是，Bessie正在玩过山车，但她感到头晕。在不超过她“头晕极限”的情况下，她最多能获得多少快乐。

输入由以下内容组成：

"N K L

N（1≤N≤1,000）是该过山车中段落的数量; K（1≤K≤500）是如果她在任何一段骑行中闭眼，Bessie晕眩级别将下降的数量; L（1≤L≤300,000）是Bessie可以容忍的晕眩极限 - 如果她的晕眩程度超过L，Bessie会生病，那肯定不好玩！

接下来的N行每行包含两个整数:

F D

F（1≤F≤20）是Bessie开着眼在该部分获得的总乐趣增加量，D（1≤D≤500）是Bessie开着眼在该部分获得的晕眩增加量。这些部分将按顺序列出。

我用的算法如下所示：

        cin >> N; // sections
        cin >> K; // amount dizziness can go down
        cin >> L; // dizzy ceiling
        belowL = L; // sets the amount of dizzy left

        for (int i = 0; i < N; i++) {
            cout << "\n" << i;
            cin >> F >> D; // fun increase and dizzy increase
            if (D < belowL) {
                if (F >= D) {
                    funTotal += F;
                }
            }
            else {
                belowL -= K;
            }

然而，这并不总是产生正确的结果。问题在哪里？它应该选择有趣的选项，除非它会使贝西超过生病的阈值。有更好的方法吗？

- Linell

---

我很好奇为什么有人投票关闭这个问题，它的措辞非常清晰，并且还附有原问题的链接。:p 我现在没有时间去阅读它，但如果我有时间，它看起来似乎是一个有趣的问题！ - John Humphreys

你应该寻找最大化总体乐趣的方法，而不是仅仅试图尽快获得尽可能多的乐趣。 - Georg Fritzsche

让我想起了《过山车大亨》游戏。我喜欢看客人从过山车上下来，在人行道上呕吐的场景。 - Fred Larson

似乎有很多可能的输入，您可以在最大乐趣（F = 20）和低于中位数的头晕（D <250）之间选择，仍然选择不将乐趣添加到总乐趣中，同时也不闭上眼睛恢复头晕。 - matthias

这是“0-1背包问题”，这是一个可以在谷歌上搜索到的术语。 - Dialecticus

Answer 1

因此，不是给你代码，而是解释一下问题的解决方法。

基本方法是使用动态规划来解决，因为这可以减少所谓的 背包问题。以这种方式考虑，她的晕眩程度就像她能一次性扛多少重量，而乐趣就是她想要最大化的东西（与她在口袋里携带的 “物品” 的价值相比）。现在我们想做的是在过山车上获得最大的快乐（在口袋中获得最大的价值），而不让她太晕（超过口袋的“重量”限制）。

所以现在你需要选择她睁开/闭上眼睛的部分（无论物品是否在口袋中）。因此，一种简单的思路是选择两种选项中的最大值。如果她可以在不超过阈值的情况下睁开眼睛，或者选择闭上眼睛。但现在问题发生了变化，你会发现，如果她睁开眼睛，她的晕眩阈值将会降低（易于解决子问题）。

使用这些信息，可以很容易地将背包解决方案调整为此问题，而不必使用回溯或递归。

这个想法是将所有先前解决的子问题保存在矩阵中，以便您可以重复使用结果，而不是每次重新计算它们。请注意，您可以使用一个技巧，即只需要矩阵的当前行和先前已解决的行，因为背包问题的递归关系仅需要这些条目 :)

附言：我曾经参加过这个问题所在的区域，并解决了它，很高兴再次看到这个问题。

- Jesus Ramos

Answer 2

如果不会使Bessie超过生病的阈值，应该选择有趣的选项。有更好的方法吗？

问题在于你并没有最大化乐趣，只是防止Bessie生病。当你到达一个可能使她超过头晕限制的部分时，可以通过回溯并在一些之前的部分选择不有趣的选项来增加更多的乐趣。假设你有类似以下的输入，以F D顺序：

1 400
5 450
10 25
18 75
20 400

此外，假设她在到达上面的第一部分时已经接近晕眩的极限。你可以选择在前两个部分中选择有趣的选项，这会使F值增加6，D值增加850。也许这会让她接近极限。现在，你别无选择，只能选择后续部分的不那么有趣的选项。另一方面，如果你在前两个部分中选择了不那么有趣的选项，那么你可以在接下来的三个部分中选择有趣的选项，这将使F值增加48，但只会增加500的D值。

目前的算法会在F:D比大于1且剩余的晕眩容量足够时选择有趣的选项。这是合理的，但并不是最优的。可能没有固定的比率能给出最优解。相反，你需要考虑每个部分的每个选项的收益和成本。

- Caleb