题解：P1048 [NOIP2005 普及组] 采药

· · 题解

背包问题

本题在读完题目后，会发现这是一道经典的 01 背包问题。

我们回顾下如何求解 01 背包问题：

首先假设每件物品的体积为 v_{i}，价值为 w_{i}。

定义状态为 f_{i,j} 表示前 i 个物品，容量为 j 的情况下的最优解。

初始化为 f_{0,0}为 0 。

接下来是状态转移:

当前的物品可以选也可以不选。

若不选第 i 件物品，则状态为 f_{i-1,j}。

若选第 i 件物品，则状态为 f_{i-1,j-v_{i}}+w_{i}。

我们要求最优解，因此在以上两种情况求最大值即可。

再回看这道题：采摘某株草药的时间其实就是物品的体积，草药的价值其实就是物品的价值。

因此我们使用动态规划 01 背包算法即可得到正确答案。

以下是代码：

#include<iostream>
using namespace std;
const int N = 1e3+5;
int T,m,f[N],v[N],w[N];
int main()
{
    cin>>T>>m;
    for(int i = 1;i<=m;i++)
        cin>>v[i]>>w[i];
    for(int i = 1;i<=m;i++)
        for(int j = T;j>=v[i];j--)
            f[j] = max(f[j],f[j-v[i]]+w[i]);
    cout << f[T] << endl;
    return 0;
}