Acwing 5. 多重背包问题 II

 本题朴素做法与完全背包类似，那么优化解法是不是也可以借鉴完全背包那样呢？

答案是否定的，因为完全背包中的物品有无限个，而多重背包中的物品是有限个，两个公式不能进行合并（有点级数的意思？），也就是说，max函数不能通过总体的最大值减去最后一项的最大值得到前面的最大值。

此处采用二进制优化多重背包，将优化后的多重背包视为0/1背包进行求解。

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 15000;

int f[N], v[N], w[N];
int n, 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;
}