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

· · 题解

思路

经典 01背包 问题。观察到题目中含有「时间」与「价值」字样，考虑使用 背包 求解。

定义 w_i 表示采药时间，c_i 表示药的价值和数组 f_{i,v}，表示采前 i 株草药花费 v 个单位时间获得的最大价值。显见，对于前 i 株草药，可以选择采与不采第 i 株草药，采后会花费 w_i 的时间。根据上文，我们可以列出转移方程：

f_{i,v} \gets \max(f_{i-1,v},f_{i-1,v-w_i} + c_i)

其中，f_{i-1,v} 表示不采这株草药的价值，f_{i-1,v-w_i} + c_i 表示采这株草药的价值，我们要取二者最大值。

显见最后输出结果为 f_{M,T}。

时间复杂度为 O(TM)。

实现

# include <iostream>
using namespace std;
int w[1145],c[1145],f[1145][1145];
int main(){
    int n,m; cin >> m >> n;
    for (int i = 1;i <= n;i++) cin >> w[i] >> c[i];
    for (int i = 1;i <= n;i++){
        for (int v = m;v > 0;v--){
            if (w[i] <= v) f[i][v] = max(f[i-1][v],f[i-1][v-w[i]]+c[i]);
            else f[i][v] = f[i-1][v];
        }
    }cout << f[n][m];
    return 0;
}