题解：[NOIP2005 普及组] 采药

· · 题解

一道 0-1 背包模版题。

首先对于每株草药，只有两种情况：取或不取。那么我们就可以设一个数组（出于考虑有同学没学过动态规划，所以暂时不叫他 DP 状态），f_{i,j}=k 表示只采前 i 株草药，时间为 j 时，最多能采到总价值为 k 的草药。

这样我们就可以开始考虑如何得到 f_{i,j}。假如我们已经处理好了前 i-1 株采药的所有情况，那么对于第 i 株草药，我们就可以分两种情况：

  1. 如果不取，那么就很简单，f_{i,j} 还是等于 f_{i-1,j}。
  2. 如果取，这时候剩余的时间就会减少采这株采药所需的时间（t_i），但总价值就会加上这株草药的价值（v_i），所以这时候 f_{i,j} 就会等于 f_{i-1,j-t_i}+v_i。

考虑完两种情况后，我们只需要找他们两个中更优的方案，让 f_{i,j}=\max(f_{i-1,j},f_{i-1,j-t_i}+v_i) 就可以了，我们管这个公式叫转移方程。

这样我们就可以得到代码了：

核心代码

for(int i = 1; i <= M; i++)
    for(int j = 0; j <= T; j++)
        f[i][j] = max(f[i-1][j], f[i-1][j-t[i]]+v[i]);

但是如果你这么交上去的话就会发现全都 \texttt{WA} 了，这是为什么呢？

其实我们仔细观察第 2,3 行，我们的 j 从 1 开始枚举，但是转移方程中有这样一个东西：j-t[i]。这样是不是就发现问题了？如果 j 要是小于 t_i 怎么办？所以我们的 j 要按 T \to 0 枚举，并在代码中加一个判断，这样就可以完美解决这个问题：

完整代码

#include <iostream>
using namespace std;

const int N = 1e3+5;
int t[N], v[N];
int f[105][N];

int main()
{
    int T, M;
    cin >> T >> M;
    for(int i = 1; i <= M; i++)
        cin >> t[i] >> v[i];
    for(int i = 1; i <= M; i++)
        for(int j = T; j >= 0; j--)
        {
            if(j >= t[i])
                f[i][j] = max(f[i-1][j], f[i-1][j-t[i]]+v[i]);
            else
                f[i][j] = f[i-1][j];
        }
    cout << f[M][T] << endl;
    return 0;
}

于是，我们就顺利通过此题了！

但是我们其实还可以将 f 数组优化成一维的，接下来就来看一看如何优化。

如果大家有空间这个概念的话，就应该思考一个问题：如果题目中 M,T 的更大怎么办？如果开二维数组就有可能出现 \texttt{MLE}，这时候我们就需要对代码进行优化。

首先来看，当我们处理到第 i 株草药时，不难发现，对 f_i 有影响的只有 f_{i-1}，所以可以直接去掉第一维，直接用 f_j=k 表示当总时间为 j 时，最多可获得总价值为 k 的草药。于是就可以得出转移方程：f_j=\max(f_j,f_{j-w_i}+v_i)，这样代码是不是就十分简单了呢？但可能有人说，这样会重复放入。

说的没错，仔细观察代码可以发现：当 j\geq t_i 时，f_{i,j} 会被 f_{i,j-t_i} 影响，因此第 i 株草药会被多次采摘。如果想解决这个问题其实也很简单，我们只需改变枚举顺序，按 T \to t_i 枚举，这时 f_{i,j} 就会在 f_{i,j-t_i} 前更新了。所以代码就是如下所示：

AC Code

#include <iostream>
using namespace std;

const int N = 1e3+5;
int t[N], v[N];
int f[N];

int main()
{
    int T, M;
    cin >> T >> M;
    for(int i = 1; i <= M; i++)
        cin >> t[i] >> v[i];
    for(int i = 1; i <= M; i++)
        for(int j = T; j >= t[i]; j--)
            f[j] = max(f[j], f[j-t[i]]+v[i]);
    cout << f[T] << endl;
    return 0;
}

是不是非常简短呢？

后记

其实背包问题不光只有 0-1 背包，还有完全背包、多重背包等变形问题。如果你还想学习这些问题，可以参考这里。

最后，希望这篇题解可以帮到你，祝你在 OI 的路上越走越远，慢慢喜欢上编程，获得更多成就！