思路

刚学完背包问题，比较熟悉。每个物品的个数有限制----> 多重背包问题

1. 用多重背包考虑的时候有两个问题，数据范围太大， 考虑二进制优化；题目要求某种的物品不能使用，我们考虑如何解决。

2. 二进制优化比较简单，我们把每种物品的数量按照：1，2，4，.... , 2^n, 打包。

3. 第i个物品不能使用，我们要找到第i个物品打包之后，被分在了那几个包。我们可以用l[i], r[i]，记录每个物品打包之后被分的包的左右端点。

4. 因为中间被断开了一部分，所以我们要预处理两个f[i][j], 其中fl[i][j], 表示从左到右（1 ~ i）的最大值，fr[i][j]表示从右到左的（cnt ~ j ）的最大值。

5. 最后更新的时候，我们枚举前半部分和后半部分的体积：i 和 m-i，res = max(res, f[l[de]][i] + fr[r[de]][va - i]);

6. 注意一点，我们从右到左更新的时候，f[i - i][j] , 应该换为f[i + 1][j], 因为后边的物品是我们先更新的。

7. 数据范围的问题：主要考虑最多分几个包。每种物品最多有1000个，最多分10个包；所以总的cnt < 1000 * 10 = 10000。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;

const int N = 1010;
int fl[10010][N], fr[10010][N];
int w[10010], v[10010];
int l[10010], r[10010]; //表示每种物品打包之后的划分范围
int main()
{
    int n, cnt = 0;
    cin >> n;
    for(int i = 1; i <= n; i ++)
    {

        int vv, ww, sum;
        cin >> vv >> ww >> sum;
        int k = 1;
        l[i] = cnt;
        while(k <= sum)
        {
            cnt ++;
            v[cnt] = vv * k;
            w[cnt] = ww * k;
            sum -= k;
            k *= 2;
        }
        if(sum > 0)
        {
            cnt ++;
            v[cnt] = sum * vv;
            w[cnt] = sum * ww;
        }
        r[i] = cnt + 1;
    }
    for(int i = 1; i <= cnt; i ++)
    {
        for(int j = 0; j < N; j ++)
        {
            fl[i][j]  = fl[i - 1][j];
            if(j >= v[i]) fl[i][j] = max(fl[i][j], fl[i - 1][j - v[i]] + w[i]);
        }
    }
    for(int i = cnt ; i >= 1; i --)
    {
        for(int j = 0; j < N; j ++)
        {
            fr[i][j] = fr[i + 1][j];
            if(j >= v[i]) fr[i][j] = max(fr[i][j], fr[i + 1][j - v[i]] + w[i]);
        }
    }
    int op;
    cin >> op;
    while(op --)
    {
        int de, m;
        cin >> de >> m;
        de ++;
        int res = 0;
        for(int i = 0; i <= m; i ++)
        {
            res = max(res, fl[l[de]][i] + fr[r[de]][m - i]);
        }
        cout << res << endl;
    }
    return 0 ;
}