入门级-多重背包及其他类型背包

# 多重背包

[YBTJ1269【例9.13】庆功会](http://39.99.183.126:8888/p/YBTJ1269)

---

## 1、多重背包问题

有一个容量为V的背包和N种物品，第i种物品的体积是c[i]，价值是w[i]。每种物品最多可选a[i]个，求将哪些物品装入背包使得价值总和最大。

---

## 2、状态转移方程

与完全背包很像，区别就在于每个物品有上限a[i]，因此状态方程为：

```
dp[i][j] = max(dp[i-1][j-k*c[i]] + k*w[i]),  0<=k<=min(j/c[i], a[i])
```

---

## 3、朴素算法

三重循环：

```
for(int i=1; i<=n; i++) //物品
for(int j=v; j>=0; j--) //容量
  for(int k=0; k<=min(j/c[i], a[i]); k++) //个数
    f[j] = max(f[j], f[j-k*c[i]] + k*w[i]);
```

---

## 4、二进制拆分

把第i件物品拆分成多个物品，体积为 $c[i]\*2^k$，价值为$w[i]\*2^k$，其中 $k$ 满足 $c[i]\*2^k\le v$，这样，多重背包问题就转化成了01背包问题，即每个物品只能选或者不选。

```c
for(int i=1; i<=n; i++) {//把i物品的a[i]个拆成若干个虚拟物品
  int s = a[i];
  for(int j=1; j<=s; j*=2) {
    c2[++last] = j*c[i];
    w2[last] = j*w[i];
    s -= j;
  }
  if(s) {//还有剩余
    c2[++last] = s * c[i];
    w2[last] = s * w[i];
  }
}
```

---

这样拆分的依据：对于第i件物品，不管选择几件，都可以用若干个2^k的和。例如：

```
0 = 都不选
1 = 2^0
2 = 2^1
3 = 2^1 + 2^0
```

于是，接下来就可以愉快的用01背包了。

---

## 混合背包

混合背包就是将前面三种的背包问题混合起来，有的只能取一次，有的能取无限次，有的只能取 $k$ 次。

这种题目看起来很吓人，可是只要领悟了前面几种背包的中心思想，并将其合并在一起就可以了。下面给出伪代码：

```plain
for (循环物品种类) {
  if (是 0 - 1 背包)
    套用 0 - 1 背包代码;
  else if (是完全背包)
    套用完全背包代码;
  else if (是多重背包)
    套用多重背包代码;
}
```

---

### 例题

[「Luogu P1833」樱花](https://www.luogu.com.cn/problem/P1833)
    有 $n$ 种樱花树和长度为 $T$ 的时间，有的樱花树只能看一遍，有的樱花树最多看 $A_{i}$ 遍，有的樱花树可以看无数遍。每棵樱花树都有一个美学值 $C_{i}$，求在 $T$ 的时间内看哪些樱花树能使美学值最高。

```cpp
for (int i = 1; i <= n; i++) {
  if (cnt[i] == 0) {  // 如果数量没有限制使用完全背包的核心代码
    for (int weight = w[i]; weight <= W; weight++) {
      dp[weight] = max(dp[weight], dp[weight - w[i]] + v[i]);
    }
  } else {  // 物品有限使用多重背包的核心代码，它也可以处理0-1背包问题
    for (int weight = W; weight >= w[i]; weight--) {
      for (int k = 1; k * w[i] <= weight && k <= cnt[i]; k++) {
        dp[weight] = max(dp[weight], dp[weight - k * w[i]] + k * v[i]);
      }
    }
  }
}
```
---

## 分组背包

[「Luogu P1757」通天之分组背包](https://www.luogu.com.cn/problem/P1757)
有 $n$ 件物品和一个大小为 $m$ 的背包，第 $i$ 个物品的价值为 $w_i$，体积为 $v_i$。同时，每个物品属于一个组，同组内最多只能选择一个物品。求背包能装载物品的最大总价值。

这种题怎么想呢？其实是从「在所有物品中选择一件」变成了「从当前组中选择一件」，于是就对每一组进行一次 0-1 背包就可以了。

再说一说如何进行存储。我们可以将 $t_{k,i}$ 表示第 $k$ 组的第 $i$ 件物品的编号是多少，再用 $\mathit{cnt}_k$ 表示第 $k$ 组物品有多少个。

### 实现

```cpp
for (int k = 1; k <= ts; k++)          // 循环每一组
  for (int i = m; i >= 0; i--)         // 循环背包容量
    for (int j = 1; j <= cnt[k]; j++)  // 循环该组的每一个物品
      if (i >= w[t[k][j]])             // 背包容量充足
        dp[i] = max(dp[i],
                    dp[i - w[t[k][j]]] + c[t[k][j]]);  // 像0-1背包一样状态转移
```

---

## 二维费用背包

[「Luogu P1855」榨取 kkksc03](https://www.luogu.com.cn/problem/P1855)"
有 $n$ 个任务需要完成，完成第 $i$ 个任务需要花费 $t_i$ 分钟，产生 $c_i$ 元的开支。

现在有 $T$ 分钟时间，$W$ 元钱来处理这些任务，求最多能完成多少任务。

这道题是很明显的 0-1 背包问题，可是不同的是选一个物品会消耗两种价值（经费、时间），只需在状态中增加一维存放第二种价值即可。

这时候就要注意，再开一维存放物品编号就不合适了，因为容易 MLE。

### 实现

```cpp
for (int k = 1; k <= n; k++)
  for (int i = m; i >= mi; i--)    // 对经费进行一层枚举
    for (int j = t; j >= ti; j--)  // 对时间进行一层枚举
      dp[i][j] = max(dp[i][j], dp[i - mi][j - ti] + 1);
```

---

## 有依赖的背包

[「Luogu P1064」金明的预算方案](https://www.luogu.com.cn/problem/P1064)
金明有 $n$ 元钱，想要买 $m$ 个物品，第 $i$ 件物品的价格为 $v_i$，重要度为 $p_i$。有些物品是从属于某个主件物品的附件，要买这个物品，必须购买它的主件。
    
目标是让所有购买的物品的 $v_i \times p_i$ 之和最大。

考虑分类讨论。对于一个主件和它的若干附件，有以下几种可能：只买主件，买主件 + 某些附件。因为这几种可能性只能选一种，所以可以将这看成分组背包。

如果是多叉树的集合，则要先算子节点的集合，最后算父节点的集合。

---

## 杂项

### 小优化

根据贪心原理，当费用相同时，只需保留价值最高的；当价值一定时，只需保留费用最低的；当有两件物品 $i,j$ 且 $i$ 的价值大于 $j$ 的价值并且 $i$ 的费用小于 $j$ 的费用时，只需保留 $i$。