01背包P1048 [NOIP 2005 普及组] 采药

P1048 [NOIP 2005 普及组] 采药
题目来源-洛谷网

题意

• 山洞里有M株草药，采第i株草药耗时t[i]，价值w[i]。
• 要在时间T内采一些草药，使得草药的价值和最大。

思路

贪心只能局部求解，典型的01背包，表格法求解

对于f[i] [j]，有两种选择：

• 不采第i株草药，价值和为f[ i-1] [j]
• 采第i株草药，价值和为f[i-1] [j-t[i]]+w[i] (j>=t[i]）在两种选择中取较大值即可得到f[i] [j]。
• 动态转移方程： f[i][j] = max(f[i-1][j],f[i-1][j-t[i]]+w[i]);

由于数据只和上一行中j行之前的数据有关，可以直接压缩成一维数组，从后往前遍历即可（保证j行之前的数据先被用，然后再更新） f[j] = max(f[j],f[j-t[i]]+w[i]);

参考代码

#include <bits/stdc++.h>
using namespace std;
int t[105], w[105], f[105][1005];
int main() {int T, M;cin >> T >> M;for (int i = 1; i <= M; i++)cin >> t[i] >> w[i];for (int i = 1; i<=M; i++) // 枚举第一个到最后一个草药for (int j = 1;j<=T; j++) {// 枚举 0 秒到 T 秒f[i][j] = f[i-1][j]; // 不选第 i 株草药-必须要处理，如果时间不够采药，是不会进入下一步 if (j>=t[i])     // 如果时间足够采第 i 株f[i][j] = max(f[i-1][j],f[i-1][j-t[i]]+w[i]); // 尝试采摘，看会不会收益更大}cout << f[M][T] << endl;  return 0;
}