本问题以C++为准

多重背包大家都很熟悉吧

它的优化从低到高如下

• 朴素 - 多重背包I
• 二进制 - 多重背包II
• 单调队列 - 多重背包III

显然，二进制优化的代码是跑不过 多重背包III 的

但是我们可以在代码前面开挂：

#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")

二进制优化版本加上挂之后平均跑 372ms
单调队列优化版本平均约跑 1499ms
单调队列优化版本加上挂之后平均约跑 860ms
注：以上均为3次测验的平均

可以明显看出，二进制版本加上挂比单调队列快很多
但是二进制版本不加挂是跑不过去的，单调队列却可以

???

所以事实证明算法的优劣不决定成败，高铁头才是王道

望解答开挂单调队列不如开挂二进制的原因

送关注一个

附录：

以下代码均由 yxc 大佬提供

单调队列优化代码

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 20010;

int n, m;
int f[N], g[N], q[N];

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i ++ )
    {
        int v, w, s;
        cin >> v >> w >> s;
        memcpy(g, f, sizeof f);
        for (int j = 0; j < v; j ++ )
        {
            int hh = 0, tt = -1;
            for (int k = j; k <= m; k += v)
            {
                if (hh <= tt && q[hh] < k - s * v) hh ++ ;
                while (hh <= tt && g[q[tt]] - (q[tt] - j) / v * w <= g[k] - (k - j) / v * w) tt -- ;
                q[ ++ tt] = k;
                f[k] = g[q[hh]] + (k - q[hh]) / v * w;
            }
        }
    }

    cout << f[m] << endl;

    return 0;
}

二进制优化代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010, M = 20010;

int n, m;
int v[N], w[N];
int f[M];

int main()
{
    cin >> n >> m;

    int cnt = 0;
    for (int i = 1; i <= n; i ++ )
    {
        int a, b, s;
        cin >> a >> b >> s;
        int k = 1;
        while (k <= s)
        {
            cnt ++ ;
            v[cnt] = a * k;
            w[cnt] = b * k;
            s -= k;
            k *= 2;
        }
        if (s > 0)
        {
            cnt ++ ;
            v[cnt] = a * s;
            w[cnt] = b * s;
        }
    }

    n = cnt;

    for (int i = 1; i <= n; i ++ )
        for (int j = m; j >= v[i]; j -- )
            f[j] = max(f[j], f[j - v[i]] + w[i]);

    cout << f[m] << endl;

    return 0;
}

臭氧：

#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
这个是从cht的打卡里拿来的

提问于3天前

wx090708

9817