返回上一级检索目录 《背包模型》

多重背包问题

问题

有$N$件物品和一个容量是$V$的背包。
第$i$件物品最多有$s_i$件，每件体积是$v_i$，价值是$w_i$。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

分析

状态转移方程
$$ f(i,j) = \max_{k=0}^{\min(s_i,\lfloor \frac{j}{v_i} \rfloor)}\{f(i-1,j-k \times v_i)+k \times w_i\} $$

代码模板

朴素版

for (int i=1; i<=n; i++) {
    for (int j=1; j<=m; j++) {
        for (int k=0; k<=s[i] && k*v[i]<=j; k++) {
            f[i][j] = max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
        }
    }
}

二进制优化

对于$s_i$件第$i$件物品，将其按$2^0,2^1,2^2,\dots,2^k,c$的个数打包分成若干组($k$是满足$\sum\limits_{i=0}^k 2^i \leq s_i$的最大整数,$c=s_i-\sum\limits_{i=0}^k 2^i$)，枚举每一组选或不选的情况，即可得到选$0 \sim s_i$个第$i$件物品的所有情况。

#include <bits/stdc++.h>
using namespace std;
const int N=25000,M=2010;
int n,m;
int v[N],w[N],cnt;
int f[N];
int main() {
    cin >> n >> m;
    for (int i=1; i<=n; i++) {
        int a,b,s;
        cin >> a >> b >> s;
        int k=1;
        while (k <= s) {
            cnt++;
            v[cnt] = a*k;
            w[cnt] = b*k;
            s -= k;
            k *= 2;
        }
        if (s) {
            cnt++;
            v[cnt] = a*s;
            w[cnt] = b*s;
        }
    }
    n = cnt;
    for (int i=1; i<=n; i++) {
        for (int j=m; j>=v[i]; j--) {
            f[j] = max(f[j],f[j-v[i]]+w[i]);
        }
    }
    cout << f[m] << endl;
    return 0;
}

单调队列优化