题目描述

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

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

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

样例

input:
4 5
1 2 3
2 4 1
3 4 3
4 5 2

output:
10

(多重背包+二进制优化) $O(V*log(size[i])$

背包九讲有详细说明，大致内容就是：
- 当容量不足以装下某种物品的有限个数和时，和该物品无限多没啥区别，因为再多也装不下了，所以可以用完全背包考虑这种物品;
- 否则的话就是二进制的内容了，利用把某件物品的物品数拆成各个二进制之和，就可以表示自己范围内的所有情况的物品数，而把这几个二进制倍的物品套上01背包就是相当于考虑该物品0-size[i]的情况。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
const int maxn = (int)1e2+5;

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

void ZeroOnePack (int cost, int value) {
    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;
}