问题本身可以在here中找到。要点是Bessie坐过山车,但她头晕目眩。她在不超过“头昏眼花的极限”的情况下可以得到的最大乐趣是多少。
输入包括:

“N K L

其中N(1≤N≤1,000)是此特定的过山车的分段数; K(1≤K≤500)是Bessies头晕目眩的程度,如果她在乘车的任何部分保持双眼紧闭都会降低。 L(1≤L≤300,000)是Bessie可以忍受的头晕极限-如果她的头晕变得比L大,Bessie就会生病,那就不好玩了!

接下来的N行中的每行将有两个整数:

D

其中F(1≤F≤20)是 shell 在该部分保持睁开的视线所获得的Bessies总乐趣的增加量,而D(1≤D≤500)是在保持视线的情况下其头晕程度的增加量在该部分打开。这些部分将按顺序列出。”

我解决这个问题的算法如下:

        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;
            }

但是,这并不总是能产生正确的结果。问题是什么?它应该选择有趣的选项,除非它将使Bessie超过疾病阈值。有更好的方法吗?

最佳答案

因此,不是给您代码,而是对问题解决方案的一种解释。

基本方法是解决使用动态编程的问题,因为这可以简化为Knapsack problem。这样想,她的头晕即是她可以立即携带多少麻袋,而乐趣就是她想要最大化的乐趣(相比之下,她在麻袋中携带的“物品”的值(value))。现在,我们想做的就是从过山车中获得最大的享受(麻袋中的最大值(value)),而又不会让她太头晕(超过麻袋的“重量”限制)。

因此,现在您要选择她睁开或闭上眼睛的部分(无论物品是否在麻袋中)。因此,考虑这一点的简便方法是同时选择两个选项中的最大值。如果她可以睁开眼睛而不会超过阈值,或者是否只睁开眼睛。但是现在问题发生了变化,您会发现她是否睁开眼睛,头晕阈值会降低(更容易解决子问题)。

使用此信息,很容易使背包解决方案适应此问题,而不必使用回溯或递归。

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

附言:我在这个问题已经解决的地区,很高兴再次看到这个问题

07-24 09:44
查看更多