E8 混合背包 • EH's Blog

题目情境#

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

题目描述

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

物品一共有三类：

第一类物品只能用 $1$ 次（ $01$ 背包）；

第二类物品可以用无限次（完全背包）；

第三类物品最多只能用 $s_i$ 次（多重背包）；

每种体积是 $v_i$ ，价值是 $w_i$ 。

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

输出最大价值。

不允许复制多重背包的代码。重新写

输入格式

第一行两个整数， $N，V$ ，用空格隔开，分别表示物品种数和背包容积。

接下来有 $N$ 行，每行三个整数 $v_i,w_i,s_i$ ，用空格隔开，分别表示第 $i$ 种物品的体积、价值和数量。

$s_i=−1$ 表示第 $i$ 种物品只能用 $1$ 次； $s_i=0$ 表示第 $i$ 种物品可以用无限次； $si\gt 0$ 表示第 i 种物品可以使用 $s_i$ 次。

输出格式

输出一个整数，表示最大价值。

输入 #1

plaintext

输出 #1

plaintext

算法解析：#

混合背包包含 01 / 完全 / 多重背包：对每件物品按类型处理——01 背包容量逆序、完全背包正序、多重背包用二进制拆分转 01 背包。本题中 $s=-1$ 表示只能取 1 件（01）， $s=0$ 表示无限件（完全）， $s>0$ 表示有 $s$ 件（多重）。复杂度 $O(nm\log s)$ 。

C++代码实现#

#include <iostream>
using namespace std;

int f[1010];

int main(){
  int n, m, v, w, s;
  scanf("%d %d", &n, &m);
  for(int i=1; i<=n; i++){  //枚举物品种类
    scanf("%d%d%d",&v,&w,&s);
    if(s!=0){               //01背包或多重背包
      if(s==-1) s=1;                
      int num=min(s,m/v);
      for(int k=1; num>0; k<<=1){
        if(k>num) k=num;
        num-=k;
        for(int j=m; j>=v*k; j--)
          f[j]=max(f[j],f[j-v*k]+w*k);
      }
    }
    else{                   //完全背包
      for(int j=v; j<=m; j++)
        f[j]=max(f[j],f[j-v]+w);
    }
  }
  printf("%d\n", f[m]);
}