背包九讲学习笔记与例题（三）

3 多重背包问题

3.1 题目

有 种物品和一个容量为 的背包。第 i 种物品最多有件可用，每件耗费的 空间是 ，价值是 。求解将哪些物品装入背包可使这些物品的耗费的空间总和不超过背包容量，且价值总和最大。

3.2 朴素算法

我们可以讲个物品拆分，则得到个物品。将原问题转化成01背包问题，时间复杂度为。
状态转移方程为：

3.3 优化

利用二进制思想，讲第种物品分成若干件物品，可以有，等等。这样件物品至多拆分成件物品。

for (int i = 1; i <= n; i++) {
    int num = min(p[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);
    }
}

3.4 例题

洛谷P1776 宝物筛选

#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <string>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

int n, m;
int a, b, c, cnt;
int dp[100000];
int v[100000];
int w[100000];

int main()
{
    scanf("%d%d",&n, &m);
    
    for(int i=1; i<=n; ++i)
    {
        scanf("%d%d%d",&a,&b,&c);
        for(int j=1; j<=c; j<<=1)
        {
            v[++cnt] = j*a;
            w[cnt] = j*b;
            c -= j;
        }
        if(c)
        {
            v[++cnt] = c*a;
            w[cnt] = c*b;
        }
    }
    
    for(int i=1; i<=cnt; ++i)
    {
        for(int j=m; j>=w[i]; --j)
        {
            dp[j] = max(dp[j-w[i]] + v[i], dp[j]);
        }
    }
    cout<<dp[m]<<endl;
    
    
    return 0;
}