确定最大乐趣的算法

Question

问题本身可以在这里找到.它的主旨是Bessie坐过山车,但她头晕目眩.如果不超过她的"晕眩极限",她可以获得的最大乐趣是多少.输入包括:

" NKL

其中N(1≤N≤1,000)是特定过山车中的截面数; K(1≤K≤500)是如果她在骑行的任何部分闭上眼睛,Bessies头晕水平下降的量; 和L(1≤L≤300,000)是Bessie可以忍受的头晕的极限 - 如果她的头晕变得比L大,Bessie会生病,那不好玩!

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

FD

其中F(1≤F≤20)是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超过疾病阈值.有没有更好的方法呢？

Answer 1

所以不要在这里给你代码,而是对问题解决方案的一种解释.

基本方法是使用动态编程来解决,因为这会减少到所谓的背包问题.想到这一点,她的头晕是她能够立刻携带多少钱而且她想要最大化的乐趣(相比之下,她在麻袋里携带的"物品"的价值).现在我们想要做的是从过山车中获得最大的乐趣(最大的价值在于麻袋)而不会让她太晕眩(超过麻袋上的"重量"限制).

所以现在你想要选择她的眼睛打开/关闭的部分(物品是否在袋中).因此,想到这一点的简单方法是选择两个选项的最大值.如果她能够在不超过门槛的情况下睁大眼睛,或者是否只是闭着眼睛.但现在问题发生了变化,你看她是否睁着眼睛,她的眩晕阈值会降低(更容易解决子问题).

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

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

PS我在这个问题给出的区域并解决了它,很高兴再次看到这个问题

Answer 2

它应该选择有趣的选项,除非它会使Bessie超过疾病阈值.有没有更好的方法呢？

问题是你没有最大化这里的乐趣,你只是阻止贝茜生病.当你到达一个会让她超过头晕目标的部分时,你可以通过回溯和在之前的部分中选择无趣的选项来增加更多的乐趣.假设你有这样的输入,按FD顺序:

1 400
5 450
10 25
18 75
20 400

此外,让我们说当她击中上面的第一部分时,她已经接近眩晕极限了.你可以在前两个部分采取有趣的选项,并获得F增加6和D增加850.也许这使她正确的极限.现在你别无选择,只能为后续部分选择无趣的选项.另一方面,如果您对前两个部分采用了不有趣的选项,则可以为接下来的三个部分选择有趣的选项,并将F增加48,D增加仅为500.

如果F:D比率大于1并且您有足够的头晕能力,那么您当前的算法会采用有趣的选项.这是合理的,但不是最优的.没有固定比率可能会给出最佳解决方案.相反,您需要考虑每个部分的每个选项的收益和成本.