题目描述

有 N 种物品和一个容量是 V 的背包。

第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。

样例

4 5
1 2 3
2 4 1
3 4 3
4 5 2

10

算法

二进制拆分（300+ms）

emm，为啥跑得比单调队列优化的快，你们单调队列都跑多快？

C++ 代码

#include <bits/stdc++.h>

using namespace std;
const int maxn = (int)2e4+5;

int val[maxn],cst[maxn],sze[maxn],N,V;
int dp[maxn];

void ZeroOnePack (int cost, int value) { //01背包
    for (int i = V; i >= cost; i--) {
        dp[i] = max(dp[i], dp[i-cost]+value);
    }
}

void CompletePack (int cost, int value) { //完全背包
    for (int i = cost; i <= V; i++) {
        dp[i] = max(dp[i], dp[i-cost]+value);
    }
}

void MultiplePack (int idx) { //多重背包
    if (sze[idx]*cst[idx] >= V) {
        CompletePack(cst[idx], val[idx]);
        return ;
    }
    int x = 1;
    int num = sze[idx];
    while (x <= num) {
        ZeroOnePack(x*cst[idx], x*val[idx]);
        num -= x; //拆为多个二进制数
        x <<= 1;
    }
    if (num > 0) {
        ZeroOnePack(num*cst[idx], num*val[idx]);
    }
}

int main() {
    cin >> N >> V;
    for (int i = 0; i < N; i++) {
        cin >> cst[i] >> val[i] >> sze[i];
    }
    memset(dp, 0, sizeof(dp));
    for (int i = 0; i < N; i++) {
        MultiplePack(i);
    }
    cout << dp[V] << endl;
    return 0;
}