庆功会

略读一遍题意之后，不难发现题目的一大特点就是每个商品的数量是有限的，完美符合了多重背包问题，如下是二进制法实现的代码：

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

using namespace std;

const int N = 1e5 +10;

int cnt;
int n, m;
int v[N], w[N], s[N];
int d[N];

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++ )
    {
        int k = 1;
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        //二进制法存储商品信息
        while(k <= c)
        {
            cnt ++;
            v[cnt] = k * a;
            w[cnt] = k * b;
            c -= k;
            k *= 2;
        }
        if(c > 0)
        {
            cnt ++;
            v[cnt] = c * a;
            w[cnt] = c * b;
        }
    }

    //二进制化操作之后，问题被转换成了01背包问题
    n = cnt;
    for(int i = 1; i <= n; i ++ )
    {
        for(int j = m; j >= v[i]; j -- )
            d[j] = max(d[j], d[j-v[i]] + w[i]);
    }

    printf("%d", d[m]);

    return 0;
}