多重背包二进制

int n, V;
int dp[2005];

void pack01(int v, int w) {
    for (int j = V; j >= v; j--) {
        dp[j] = max(dp[j], dp[j-v] + w);
    }
}

int main() {
    cin >> n >> V;
    while (n--) {
        int v,w,s; cin >> v >> w >> s;
        int k = 1;
        while (k <= s) {
            pack01(v*k, w*k);
            s -= k;
            k <<= 1;
        }
        pack01(v*s, w*s);
    }
    int ans = 0;
    for (int j = 0; j <= V; j++) ans = max(ans, dp[j]);
    cout << ans << endl;
}

多重背包(单调队列优化)

struct node {
    int pos, val;
} q[20005];
int head = -1, tail = 0, n, V, dp[20005];

void solve(int v, int w, int s) {
    for (int j = 0; j < v; j++) {
        head = 0, tail = -1;
        q[++tail] = {0,0};
        for (int i = 1; i*v + j <= V; i++) {
            while (i - q[head].pos > s) head++;
            int cur = i*v + j;
            int val = dp[cur] - i*w;
            dp[cur] = max(dp[cur], q[head].val + i*w);

            while (head <= tail && val >= q[tail].val) tail--;
            q[++tail] = {i, val};
        }
    }
}

int main() {
    cin >> n >> V;
    for (int i = 1; i <= n; i++) {
        int v,w,s; cin >> v >> w >> s;
        solve(v,w,s);
    }
    int ans = 0;
    for (int j = 0; j <= V; j++) ans = max(ans, dp[j]);
    cout << ans << endl;
}