$\LARGE\color{orange}{刷题日记(算法提高课)}$

多重背包朴素做法是时间复杂度为 $O(n^3)$，我们考虑将其复杂度降为 $O(n^2logn)$

在这里我们优化的应当是第三重循环，将 $n$ 次循环降为 $logn$ 次

第三重循环的含义是，每种物品最多可以被选择 $s$ 次，因此我们也循环了 $s$ 次（这里我们考虑理想情况，忽略边界）

也就是说，第 $i$ 个物品的选择可以从 0 到 $s$ ，一共 $s + 1$ 种可能

现在的问题是，我们能否通过 $logs$ 个数之间的总和，凑出从 0 到 $s$ 这 $s+1$ 种不同的数

这当然是可以的，我们可以通过 2 的次幂之间的组合来完成

举个例子，1，2，4，8，这些数都是 2 的次幂

通过组合前 3 个数，我们可以表示从 1 到 $2^3-1$ 之间的任意数

通过组合前 4 个数，我们可以表示从 1 到 $2^4-1$ 之间的任意数

假设我们使用这种方法来凑出 1 到 10 之间的数时，二的次幂到底该选前几个数？

这里应该选择前 3 个数，然后差值用余数来填补

这是因为，如果选前 4 个数的话，就会出现超出的情况，这不便于我们的计算

也就是说，我们只需要用 1，2，4，10-7，这四个数便可以表示 1 到 10 之间的任意数

到此，我们便实现了将原先的 $s$ 个物品降为了 $logs$ 个物品

之后就是很简单的 01 背包的问题了

完整代码：

#include <iostream>

using namespace std;

const int N = 2e4;
int v[N], w[N];
int f[N];
int n, m;

int main()
{
    cin >> n >> m;
    int k = 1;
    for(int i = 1; i <= m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        for(int j = 1; j <= c; j *= 2)
        {
            v[k] = j * a;
            w[k] = j * b;
            k++;
            c -= j;
        }
        if(c > 0)
        {
            v[k] = c * a;
            w[k] = c * b;
            k++;
        }
    }
    n = k - 1;//记得 n 的值会发生改变
    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;
}