题解：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

背包算法即可得到正确答案。

以下是代码：

CPP

#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;
}

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

文章操作

背包问题

相关推荐

评论

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