基础背包问题（上）

博主： Faulkner
发布时间：2024 年 02 月 10 日
671 次浏览
1 条评论
2285字数
分类：默认分类

# 01背包问题

## [NOIP2005 普及组] 采药

### 题目描述

辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”

如果你是辰辰，你能完成这个任务吗？

### 输入格式

第一行有 $2$ 个整数 $T$（$1 \le T \le 1000$）和 $M$（$1 \le  M \le 100$），用一个空格隔开，$T$ 代表总共能够用来采药的时间，$M$ 代表山洞里的草药的数目。

接下来的 $M$ 行每行包括两个在 $1$ 到 $100$ 之间（包括 $1$ 和 $100$）的整数，分别表示采摘某株草药的时间和这株草药的价值。

### 输出格式

输出在规定的时间内可以采到的草药的最大总价值。

### 样例 #1

#### 样例输入 #1

```
70 3
71 100
69 1
1 2
```

#### 样例输出 #1

```
3
```

### 提示

**【数据范围】**

- 对于 $30\%$ 的数据，$M \le 10$；
- 对于全部的数据，$M \le 100$。

**【题目来源】**

NOIP 2005 普及组第三题

### 分析

将总时间 $T$ 看作背包容量，药材看作物品，要采的药材的时间看作每个物品需要的体积，这道题就是一道01背包问题。

在这个问题中，我们可以定义一个二维数组 $dp[i][j]$，其中 $i$ 表示考虑前 $i$ 株草药，$j$ 表示总共可用的采药时间。$dp[i][j]$ 的值表示在给定时间 $j$ 内能够采到的前$i$ 株草药的最大总价值。

我们可以按以下步骤进行：

1. **初始化：** $dp[0][j]$ 表示没有草药可采时的总价值，自然是0。对于 $dp[i][0]$，表示没有时间可用时的总价值，也是 0。
2. **状态转移：** 对于每一株草药 $i$ 和每个时间点 $j$，我们有两种选择：
   - 如果我们不采这株草药，那么 $dp[i][j] = dp[i-1][j]$，即前 $i$ 株草药的最大价值与前 $i-1$ 株草药的最大价值相同，因为我们没有使用额外的时间。
   - 如果我们决定采这株草药（前提是我们有足够的时间，即 $j$ 大于等于采这株草药所需的时间），那么我们可以取 $dp[i-1][j-time[i]] + value[i]$和$dp[i-1][j]$ 的最大值。数学表达如下：

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

3. **遍历所有草药和时间：** 从 1 到 $M$ 遍历所有草药，从 1 到 $T$ 遍历所有可能的时间，使用上述状态转移方程更新 $dp$ 数组。
4. **输出结果：** 最终 $dp[M][T]$将包含在给定时间 $T$ 内可以采到的草药的最大总价值。

代码实现时，为了节省空间，可以将二维 $dp$ 数组简化为一维数组，因为每个状态只依赖于前一个状态。这样，我们可以只用一个一维数组 $dp[j]$，并在更新时从后向前遍历（滚动数组）。那为何在更新时从后向前遍历呢？

观察状态转移方程，在更新 $dp[j]$ 时使用的是未被更新的 $dp[j-time[i]]$ 的值，即第 $i - 1$层的$dp[j-time[i]]$。

但如果你从前往后遍历，你会在更新 $dp[j]$ 时使用已经被更新过的 $dp[j-time[i]]$，即第 $i$ 层的 $dp[j-time[i]]$，这样是不符合上述状态转移方程的，所以我们必须从后往前遍历。如下便是一维的状态转移方程。

$$
dp[j] = 
\begin{cases} 
0 & \text{if } j = 0 \\
dp[j] & \text{if } j < time[i] \\
\max(dp[j], dp[j-time[i]] + value[i]) & \text{if } j \geq time[i]
\end{cases}
$$

### 代码

```
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 1010;

int t[N], v[N];
int T, M;
int dp[N];

int main()
{
    scanf("%d%d", &T, &M);
    for (int i = 1; i <= M; i++)
        scanf("%d%d", t + i, v + i);
  
    for (int i = 1; i <= M; i++)
    {
        for (int j = T; j >= t[i]; j--)
        {
            dp[j] = max(dp[j], dp[j - t[i]] + v[i]);
        }
    }
  
    printf("%d", dp[T]);
}
```

---

# 完全背包问题

## P1616 疯狂的采药

### 题目描述

LiYuxiang 是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同种类的草药，采每一种都需要一些时间，每一种也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”

如果你是 LiYuxiang，你能完成这个任务吗？

此题和原题的不同点：

$1$. 每种草药可以无限制地疯狂采摘。

$2$. 药的种类眼花缭乱，采药时间好长好长啊！师傅等得菊花都谢了！

### 输入格式

输入第一行有两个整数，分别代表总共能够用来采药的时间 $t$ 和代表山洞里的草药的数目 $m$。

第 $2$ 到第 $(m + 1)$ 行，每行两个整数，第 $(i + 1)$ 行的整数 $a_i, b_i$ 分别表示采摘第 $i$ 种草药的时间和该草药的价值。

### 输出格式

输出一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。

### 样例 #1

#### 样例输入 #1

```
70 3
71 100
69 1
1 2
```

#### 样例输出 #1

```
140
```

### 提示

#### 数据规模与约定

- 对于 $30\%$ 的数据，保证 $m \le 10^3$ 。
- 对于 $100\%$ 的数据，保证 $1 \leq m \le 10^4$，$1 \leq t \leq 10^7$，且 $1 \leq m \times t \leq 10^7$，$1 \leq a_i, b_i \leq 10^4$。

### 分析

这题是上面改编过来的题目，从01背包改编成了完全背包。现在直接就分析朴素完全背包，不针对题目进行分析完全背包了。

首先，定义状态和状态转移方程。设 $dp[i][j]$ 表示从前 $i$ 种物品中选取一些物品（每种物品可以选取无限次），放入容量为 $j$ 的背包中，所能获得的最大价值。

为了得到最初的状态转移方程，我们考虑对于给定的第 $i$ 种物品，选择它0次、1次、2次、... 、$t$ 次（$t$ 是满足 $t \cdot w[i] \leq j$ 的最大整数）。这样，我们可以得到最初的状态转移方程：

$$
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 - k \cdot w[i]] + k \cdot v[i] ) & \text{if } j \geq w[i]
\end{cases}
$$

其中，$k$ 是满足 $0 \leq k \leq t$ 的任意整数。

$j \geq w[i]$ 时，将上述方程展开可以得到：

$$
dp[i][j] = \max(dp[i-1][j], dp[i-1][j - w[i]] + v[i], dp[i-1][j - 2 \cdot w[i]] + 2 \cdot v[i], \ldots, dp[i-1][j - t \cdot w[i]] + t \cdot v[i])
$$

同理，将 $dp[i][j - w[i]]$ 展开可以得到：

$$
dp[i][j - w[i]] = \max(dp[i-1][j - w[i]], dp[i-1][j - 2 \cdot w[i]] + v[i], \ldots, dp[i-1][j - t \cdot w[i]] + (t - 1) \cdot v[i])
$$

将上述方程中的每一项加上 $v[i]$，我们得到：

$$
dp[i][j - w[i]] + v[i] = \max(dp[i-1][j - w[i]] + v[i], dp[i-1][j - 2 \cdot w[i]] + 2 \cdot v[i], \ldots, dp[i-1][j - t \cdot w[i]] + t \cdot v[i])
$$

比较这个方程和原始的状态转移的展开方程，我们可以看到它们的结构非常相似。事实上，$dp[i][j - w[i]] + v[i]$包含了除了 $dp[i-1][j]$ 之外的所有情况。因此，我们可以将原始的状态转移方程简化为：

$$
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][j - w[i]] + v[i]) & \text{if } j \geq w[i]
\end{cases}
$$

然后，我们来考虑如何将这个二维的方程优化为一维。观察上面的方程，状态 $dp[i][j]$ 只依赖于前一层 $dp[i-1][j]$ 的状态和当前层 $dp[i][j - w[i]]$ 的状态。因此，如果我们从小到大更新 $j$ 的值（01背包问题是从大到小更新），我们可以只使用一维数组 $dp[j]$ 来存储状态。一维状态转移方程如下：

$$
dp[j] = 
\begin{cases} 
0 & \text{if } j = 0 \\
dp[j] & \text{if } j < w[i] \\
\max(dp[j], dp[j - w[i]] + v[i]) & \text{if } j \geq w[i]
\end{cases}
$$

这里的 $dp[j]$ 代表的是当前背包容量为 $j$ 时的最大价值。

### 代码

此题和上面01背包问题的区别只在于一个时从大到小遍历$ j$ ，一个是从小到大遍历 $j$ 。所以就不再给出代码了，读者可以自己去洛谷写写这题。（注意数学范围，这题比原题数据范围大很多）

最后修改：2024 年 10 月 23 日

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

1 条评论

Faulkner
February 10th, 2024 at 05:00 pm

新年快乐

回复

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

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

基础背包问题（上）

Faulkner • 2024 年 02 月 10 日

# 01背包问题

## [NOIP2005 普及组] 采药

### 题目描述

如果你是辰辰，你能完成这个任务吗？

### 输入格式

第一行有 $2$ 个整数 $T$（$1 \le T \le 1000$）和 $M$（$1 \le  M \le 100$），用一个空格隔开，$T$ 代表总共能够用来采药的时间，$M$ 代表山洞里的草药的数目。

接下来的 $M$ 行每行包括两个在 $1$ 到 $100$ 之间（包括 $1$ 和 $100$）的整数，分别表示采摘某株草药的时间和这株草药的价值。

### 输出格式

输出在规定的时间内可以采到的草药的最大总价值。

### 样例 #1

#### 样例输入 #1

```
70 3
71 100
69 1
1 2
```

#### 样例输出 #1

```
3
```

### 提示

**【数据范围】**

- 对于 $30\%$ 的数据，$M \le 10$；
- 对于全部的数据，$M \le 100$。

**【题目来源】**

NOIP 2005 普及组第三题

### 分析

将总时间 $T$ 看作背包容量，药材看作物品，要采的药材的时间看作每个物品需要的体积，这道题就是一道01背包问题。

我们可以按以下步骤进行：

观察状态转移方程，在更新 $dp[j]$ 时使用的是未被更新的 $dp[j-time[i]]$ 的值，即第 $i - 1$层的$dp[j-time[i]]$。

$$
dp[j] = 
\begin{cases} 
0 & \text{if } j = 0 \\
dp[j] & \text{if } j < time[i] \\
\max(dp[j], dp[j-time[i]] + value[i]) & \text{if } j \geq time[i]
\end{cases}
$$

### 代码

```
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 1010;

int t[N], v[N];
int T, M;
int dp[N];

---

# 完全背包问题

## P1616 疯狂的采药

### 题目描述

如果你是 LiYuxiang，你能完成这个任务吗？

此题和原题的不同点：

$1$. 每种草药可以无限制地疯狂采摘。

$2$. 药的种类眼花缭乱，采药时间好长好长啊！师傅等得菊花都谢了！

### 输入格式

输入第一行有两个整数，分别代表总共能够用来采药的时间 $t$ 和代表山洞里的草药的数目 $m$。

第 $2$ 到第 $(m + 1)$ 行，每行两个整数，第 $(i + 1)$ 行的整数 $a_i, b_i$ 分别表示采摘第 $i$ 种草药的时间和该草药的价值。

### 输出格式

输出一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。

### 样例 #1

#### 样例输入 #1

```
70 3
71 100
69 1
1 2
```

#### 样例输出 #1

```
140
```

### 提示

#### 数据规模与约定

- 对于 $30\%$ 的数据，保证 $m \le 10^3$ 。
- 对于 $100\%$ 的数据，保证 $1 \leq m \le 10^4$，$1 \leq t \leq 10^7$，且 $1 \leq m \times t \leq 10^7$，$1 \leq a_i, b_i \leq 10^4$。

### 分析

这题是上面改编过来的题目，从01背包改编成了完全背包。现在直接就分析朴素完全背包，不针对题目进行分析完全背包了。

$$
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 - k \cdot w[i]] + k \cdot v[i] ) & \text{if } j \geq w[i]
\end{cases}
$$

其中，$k$ 是满足 $0 \leq k \leq t$ 的任意整数。

$j \geq w[i]$ 时，将上述方程展开可以得到：

$$
dp[i][j] = \max(dp[i-1][j], dp[i-1][j - w[i]] + v[i], dp[i-1][j - 2 \cdot w[i]] + 2 \cdot v[i], \ldots, dp[i-1][j - t \cdot w[i]] + t \cdot v[i])
$$

同理，将 $dp[i][j - w[i]]$ 展开可以得到：

$$
dp[i][j - w[i]] = \max(dp[i-1][j - w[i]], dp[i-1][j - 2 \cdot w[i]] + v[i], \ldots, dp[i-1][j - t \cdot w[i]] + (t - 1) \cdot v[i])
$$

将上述方程中的每一项加上 $v[i]$，我们得到：

$$
dp[i][j - w[i]] + v[i] = \max(dp[i-1][j - w[i]] + v[i], dp[i-1][j - 2 \cdot w[i]] + 2 \cdot v[i], \ldots, dp[i-1][j - t \cdot w[i]] + t \cdot v[i])
$$

$$
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][j - w[i]] + v[i]) & \text{if } j \geq w[i]
\end{cases}
$$

$$
dp[j] = 
\begin{cases} 
0 & \text{if } j = 0 \\
dp[j] & \text{if } j < w[i] \\
\max(dp[j], dp[j - w[i]] + v[i]) & \text{if } j \geq w[i]
\end{cases}
$$

这里的 $dp[j]$ 代表的是当前背包容量为 $j$ 时的最大价值。

### 代码

1 条评论

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

基础背包问题（上）

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