AcWing 7. 混合背包问题

#include 

using namespace std;
const int N = 100010;
int n;      //物品种类
int m;      //背包容量
int v[N];   //物品体积
int w[N];   //物品价值
int f[N];   //dp数组

int main() {
    cin >> n >> m;
    int cnt = 1;
    //n类物品
    for (int i = 1; i <= n; i++) {
        int a, b, s;
        //体积，价值，个数
        cin >> a >> b >> s;
        if (s < 0)s = 1;            //题目中s=-1表示只有1个
        else if (s == 0)s = m / a;  //完全背包:最多总体积/该物品体积向下取整
        //将01背包和完全背包利用二进制优化转化为多重背包
        int k = 1;
        while (k <= s) {
            v[cnt] = a * k;
            w[cnt] = b * k;
            s -= k;
            k *= 2;
            cnt++;
        }
        if (s > 0) {
            v[cnt] = s * a;
            w[cnt] = s * b;
            cnt++;
        }
    }
    //01背包模板
    for (int i = 1; i <= cnt; i++)
        for (int j = m; j >= v[i]; j--)
            f[j] = max(f[j], f[j - v[i]] + w[i]);
    //输出大吉
    printf("%d", f[m]);
    return 0;
}