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

2020-03-08 本文已影响0人风之旅人c

3 多重背包问题

3.1 题目

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

3.2 朴素算法

我们可以讲 $M_i$ 个物品拆分，则得到 $\Sigma M_i$ 个物品。将原问题转化成01背包问题，时间复杂度为 $O(V\Sigma M_i)$ 。
状态转移方程为：
$dp[i][v] = max(dp[i-1][v-k*C_i] + k*W_i ), 0<=k<=N_i$

3.3 优化

利用二进制思想，讲第 $i$ 种物品分成若干件物品，可以有 $(C_i, W_i), (C_i*2, W_i*2), (C_i*4, W_i*4)$ ，等等。这样 $n$ 件物品至多拆分成 $logn$ 件物品。

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;
}