基础背包问题（下）

博主： Faulkner
发布时间：2024 年 02 月 18 日
561 次浏览
暂无评论
2529字数
分类：默认分类

# 多重背包问题

## 宝物筛选

### 题目描述

终于，破解了千年的难题。小 FF 找到了王室的宝物室，里面堆满了无数价值连城的宝物。

这下小 FF 可发财了，嘎嘎。但是这里的宝物实在是太多了，小 FF 的采集车似乎装不下那么多宝物。看来小 FF 只能含泪舍弃其中的一部分宝物了。

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

### 输入格式

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

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

### 输出格式

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

### 样例 #1

#### 样例输入 #1

```
4 20
3 9 3
5 9 1
9 4 2
8 1 3
```

#### 样例输出 #1

```
47
```

### 提示

对于 $30\%$ 的数据，$n\leq \sum m_i\leq 10^4$，$0\le W\leq 10^3$。

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

### 分析

这题是一道多重背包问题的模板题。如果你看过基础背包问题（上）中完全背包问题的推导，你应该可以很容易的推导出这道题的状态转移方程如下：

$$
dp[i][j] =
\begin{cases}
0 & \text{if } j = 0 \text{ or } i = 0 \\
dp[i-1][j] & \text{if } j < w[i] \\
\max(dp[i-1][j], dp[i-1][j - k \cdot w[i]] + k \cdot v[i]) & \text{if } j \geq w[i] \text{ and } 1 \leq k \leq \min(m_i, \left\lfloor \frac{j}{w[i]} \right\rfloor)
\end{cases}
$$

这看起来和完全背包问题的方程类似，唯一不同的是 $k$ 的取值范围不同，完全背包中只需要保证 $k$ 大于等于1且小于等于$\left\lfloor \frac{j}{w[i]} \right\rfloor$即可，而多重背包要保证在大于等于1基础上还满足 $k \leq \min(m_i, \left\lfloor \frac{j}{w[i]} \right\rfloor$。

所以说多重背包不能用完全背包的优化方法优化。在大量输入的情况下，二进制优化可能是一个很好的选择。那何为二进制优化？

二进制优化的思路是将每种物品的数量进行二进制拆分，这样可以将物品的选取转化为01背包问题。即对于某种物品 $i$ ，其数量为 $m_i$ ，我们将其拆分为若干个物品集，每个物品集的该物品数量是递增2次幂或一个可能的剩余部分，使所有物品集中的该物品总和为 $m_i$ 。然后将每个物品集视为不同的新物品从而转化为01具体的划分为：

- 第一部分：$1, 2, 4, \ldots, 2^{k_0}$

- 剩余部分：$m_i - (1 + 2 + 4 + \ldots + 2^{k_0})$

光讲还是有点抽象，现在举一个例子：考虑一种物品，设其为物品 $i$ ，数量为 $m_i=19$ ，每个物品的价值 $v_i=5$ ，重量 $w_i=3$ 。

1. 首先将19用二进制数拆分，直到总和加上一个可能的剩余部分等于19。具体拆分如下：

- $2^0=1$个物品

- $2^1=2$个物品

- $2^2=4$个物品

- $2^3=8$个物品

- 剩余部分$19-(1+2+4+8)=4$个物品

2. 根据此拆分，我们得到以下几个新的物品：

- 1个重量为3，价值为5的物品

- 2个重量为 $2 \cdot 3=6$ ，价值为 $2 \cdot 5=10$ 的物品

- 4个重量为 $4 \cdot 3=12$ ，价值为 $4 \cdot 5=20$ 的物品

- 8个重量为 $8 \cdot 3=24$ ，价值为 $8 \cdot 5=40$ 的物品

- 额外的4个重量为 $4 \cdot 3=12$ ，价值为 $4 \cdot 5=20$ 的物品

现在，每个拆分后的物品都可以当作是在01背包问题中的物品，每个都只能选取一次。这样可以表示1 ~ 19中所有的选取数量。关于证明便不证明了。有兴趣可以自己搜搜。

### 代码

```c++
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;
int v[N], w[N], dp[N];

int main()
{
    int n, m, cnt = 0;
    int a, b, s;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++)
    {
        scanf("%d%d%d", &a, &b, &s);
        int k = 1;
        while (k <= s)
        {
            cnt ++;
            v[cnt] = a * k;
            w[cnt] = b * k;
            s -= k;
            k *= 2;
        }
        
        if (s)
        {
            cnt ++;
            v[cnt] = a * s;
            w[cnt] = b * s;
            s = 0;
        }
    }
    
    n = cnt;
    
    for (int i = 1; i <= n; i++)
    {
        for (int j = m; j >= w[i]; j--)
        {
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    }
    
    printf("%d", dp[m]);
}
```

# 分组背包问题

## 通天之分组背包

### 题目背景

直达通天路·小 A 历险记第二篇

### 题目描述

自 $01$ 背包问世之后，小 A 对此深感兴趣。一天，小 A 去远游，却发现他的背包不同于 $01$ 背包，他的物品大致可分为 $k$ 组，每组中的物品相互冲突，现在，他想知道最大的利用价值是多少。

### 输入格式

两个数 $m,n$，表示一共有 $n$ 件物品，总重量为 $m$。

接下来 $n$ 行，每行 $3$ 个数 $a_i,b_i,c_i$，表示物品的重量，利用价值，所属组数。

### 输出格式

一个数，最大的利用价值。

### 样例 #1

#### 样例输入 #1

```
45 3
10 10 1
10 5 1
50 400 2
```

#### 样例输出 #1

```
10
```

### 提示

$0 \leq m \leq 1000$，$1 \leq n \leq 1000$，$1\leq k\leq 100$，$a_i, b_i, c_i$ 在 `int` 范围内。

### 分析

易得状态转移方程为：

$$
dp[i][j] =
\begin{cases}
0, & \text{if } i = 0 \text{ or } j = 0 \\
dp[i-1][j], & \text{if } j < w_{ik} \\
\max(dp[i-1][j], dp[i-1][j-w_{ik}] + v_{ik}), & \text{if } j \geq w_{ik}
\end{cases}
$$

### 代码

很简单就不多写了

最后修改：2024 年 10 月 23 日

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

基础背包问题（下）

Faulkner • 2024 年 02 月 18 日

# 多重背包问题

## 宝物筛选

### 题目描述

终于，破解了千年的难题。小 FF 找到了王室的宝物室，里面堆满了无数价值连城的宝物。

这下小 FF 可发财了，嘎嘎。但是这里的宝物实在是太多了，小 FF 的采集车似乎装不下那么多宝物。看来小 FF 只能含泪舍弃其中的一部分宝物了。

### 输入格式

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

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

### 输出格式

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

### 样例 #1

#### 样例输入 #1

```
4 20
3 9 3
5 9 1
9 4 2
8 1 3
```

#### 样例输出 #1

```
47
```

### 提示

对于 $30\%$ 的数据，$n\leq \sum m_i\leq 10^4$，$0\le W\leq 10^3$。

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

### 分析

这题是一道多重背包问题的模板题。如果你看过基础背包问题（上）中完全背包问题的推导，你应该可以很容易的推导出这道题的状态转移方程如下：

所以说多重背包不能用完全背包的优化方法优化。在大量输入的情况下，二进制优化可能是一个很好的选择。那何为二进制优化？

- 第一部分：$1, 2, 4, \ldots, 2^{k_0}$

- 剩余部分：$m_i - (1 + 2 + 4 + \ldots + 2^{k_0})$

光讲还是有点抽象，现在举一个例子：考虑一种物品，设其为物品 $i$ ，数量为 $m_i=19$ ，每个物品的价值 $v_i=5$ ，重量 $w_i=3$ 。

1. 首先将19用二进制数拆分，直到总和加上一个可能的剩余部分等于19。具体拆分如下：

- $2^0=1$个物品

- $2^1=2$个物品

- $2^2=4$个物品

- $2^3=8$个物品

- 剩余部分$19-(1+2+4+8)=4$个物品

2. 根据此拆分，我们得到以下几个新的物品：

- 1个重量为3，价值为5的物品

- 2个重量为 $2 \cdot 3=6$ ，价值为 $2 \cdot 5=10$ 的物品

- 4个重量为 $4 \cdot 3=12$ ，价值为 $4 \cdot 5=20$ 的物品

- 8个重量为 $8 \cdot 3=24$ ，价值为 $8 \cdot 5=40$ 的物品

- 额外的4个重量为 $4 \cdot 3=12$ ，价值为 $4 \cdot 5=20$ 的物品

### 代码

```c++
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;
int v[N], w[N], dp[N];

# 分组背包问题

## 通天之分组背包

### 题目背景

直达通天路·小 A 历险记第二篇

### 题目描述

### 输入格式

两个数 $m,n$，表示一共有 $n$ 件物品，总重量为 $m$。

接下来 $n$ 行，每行 $3$ 个数 $a_i,b_i,c_i$，表示物品的重量，利用价值，所属组数。

### 输出格式

一个数，最大的利用价值。

### 样例 #1

#### 样例输入 #1

```
45 3
10 10 1
10 5 1
50 400 2
```

#### 样例输出 #1

```
10
```

### 提示

$0 \leq m \leq 1000$，$1 \leq n \leq 1000$，$1\leq k\leq 100$，$a_i, b_i, c_i$ 在 `int` 范围内。

### 分析

易得状态转移方程为：

$$
dp[i][j] =
\begin{cases}
0, & \text{if } i = 0 \text{ or } j = 0 \\
dp[i-1][j], & \text{if } j < w_{ik} \\
\max(dp[i-1][j], dp[i-1][j-w_{ik}] + v_{ik}), & \text{if } j \geq w_{ik}
\end{cases}
$$

### 代码

很简单就不多写了

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

基础背包问题（下）

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款