背包模板

​for (int i = 1; i <= n; i++)
    for (int j = V; j >= w[i]; j--)
        f[j] = max(f[j], f[j - w[i]] + v[i]);

for (int i = 1; i <= n; i++) {
    int bound = max(V - sum{w[i]...w[n]}, v[i]);
    for (int j = V; j >= bound, j--)
        f[j] = max(f[j], f[j - w[i]] + v[i]);
}

for (int i = 1; i <= n; i++)
    for (int j = w[i]; j <= V; j++)
        f[j] = max(f[j], f[j - w[i]] + v[i]);

for (int i = 1; i <= n; i++) {
    int num = min(number[i], V / w[i]);
    for (int k = 1; num > 0; k <<= 1) {
        if (k > num) k = num;
        num -= k;
        for (int j = V; j >= w[i] * k; j--)
            f[j] = max(f[j], f[j - w[i] * k] + v[i] * k);
    }
}

void (int p, int w, int v) {
    for (int j = 0; j < w; j++) { //j为w的所有组
        int head = 1, tail = 0;
        for (int k = j, i = 0; k <= V / 2; k += w, i++) {
            int r = f[k] - i * v;
            while (head <= tail and r >= q[tail].v) tail--;
            q[++tail] = node(i, r);
            while (q[head].id < i - p) head++; //需要的物品数目
            f[k] = q[head].v + i * v;
        }
    }
}