E6 多重背包 • EH's Blog

题目情境#

题目链接：https://www.luogu.com.cn/problem/P1776 ↗

题目描述

小 FF 对洞穴里的宝物进行了整理，他发现每样宝物都有一件或者多件。他粗略估算了下每样宝物的价值，之后开始了宝物筛选工作：小 FF 有一个最大载重为 $W$ 的采集车，洞穴里总共有 $n$ 种宝物，每种宝物的价值为 $v_i$ ，重量为 $w_i$ ，每种宝物有 $m_i$ 件。小 FF 希望在采集车不超载的前提下，选择一些宝物装进采集车，使得它们的价值和最大。

输入格式

第一行为两个整数 $n$ 和 $W$ ，分别表示宝物种数和采集车的最大载重。

接下来 $n$ 行每行三个整数 $v_i,w_i,m_i$ 。

输出格式

输出仅一个整数，表示在采集车不超载的情况下收集的宝物的最大价值。

输入输出样例 #1

输入 #1

plaintext

输出 #1

plaintext

对于 $100\%$ 的数据， $n\leq \sum m_i \leq 10^5$ ， $0\le W\leq 4\times 10^4$ ， $1\leq n\le 100$ 。

算法解析：#

多重背包每种物品有 $m_i$ 件。用二进制拆分：把 $m_i$ 拆成 $1,2,4,\dots,2^k$ 加余数等 $O(\log m_i)$ 组，每组当作一个“01 背包物品”（重量/价值乘对应系数），从而转化为 01 背包。复杂度 $O(nm\log m)$ 。

Python代码实现#

n, m = map(int, input().split())

v = [0] * 100005
w = [0] * 100005
f = [0] * 100005

cnt = 0
for _ in range(n):
    b, a, s = map(int, input().split())
    j = 1
    while j <= s:
        cnt += 1
        v[cnt] = j * a
        w[cnt] = j * b
        s -= j
        j <<= 1
    if s > 0:
        cnt += 1
        v[cnt] = s * a
        w[cnt] = s * b

for i in range(1, cnt + 1):
    for j in range(m, v[i] - 1, -1):
        f[j] = max(f[j], f[j - v[i]] + w[i])

print(f[m])

python

C++代码实现#

// 二进制分组优化
#include<iostream>
using namespace std;

const int N=100005;
int n,m,a,b,s;
int v[N],w[N];
int f[N];

int main(){
  cin>>n>>m;

  int cnt=0;
  for(int i=1;i<=n;i++){
    cin>>b>>a>>s;
    for(int j=1;j<=s;j<<=1){
      v[++cnt]=j*a; w[cnt]=j*b;
      s-=j;
    }
    if(s) v[++cnt]=s*a, w[cnt]=s*b;
  }

  for(int i=1;i<=cnt;i++)
    for(int j=m;j>=v[i];j--)
      f[j]=max(f[j],f[j-v[i]]+w[i]);
  cout<<f[m];
}