当前位置：首页 > news >正文

洛谷——P1048 [NOIP 2005 普及组] 采药

news 2025/8/4 8:34:28

题目链接：洛谷——P1048 [NOIP 2005 普及组] 采药

经典01背包问题，也是左程云算法讲解073必备的第一题。本次提供两个版本代码。

递归+记忆化搜索

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;int dp[1005][105];
int maxValue(int t, int i, vector<int>& mt, vector<int>& mv);int main() {int T, M;cin >> T >> M;// T表示总时间， M表示草药数目vector<int> mt(M);vector<int> mv(M);for (int i = 0; i < M; ++i) {cin >> mt[i] >> mv[i];}memset(dp, -1, sizeof(dp));cout << maxValue(T, 0, mt, mv) << endl;return 0;
}// 返回在总时间还剩t时，选择[i, m - 1]号药材的最大值
int maxValue(int t, int i, vector<int>& mt, vector<int>& mv) {if (dp[t][i] != -1) {return dp[t][i];}if (i >= mt.size() || t <= 0) {dp[t][i] = 0;return 0;}if (t - mt[i] < 0) {dp[t][i] = maxValue(t, i + 1, mt, mv);return dp[t][i];}else {int res1 = maxValue(t - mt[i], i + 1, mt, mv) + mv[i];int res2 = maxValue(t, i + 1, mt, mv);dp[t][i] = max(res1, res2);return dp[t][i];}return -1;
}

动态规划

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;int dp[1005][105];
int maxValue(int t, int i, vector<int>& mt, vector<int>& mv);int main() {int T, M;cin >> T >> M;// T表示总时间， M表示草药数目vector<int> mt(M);vector<int> mv(M);for (int i = 0; i < M; ++i) {cin >> mt[i] >> mv[i];}memset(dp, -1, sizeof(dp));//cout << maxValue(T, 0, mt, mv) << endl;for (int i = 0; i < M + 1; i++) {dp[0][i] = 0;}for (int i = 0; i < T + 1; ++i) {dp[i][M] = 0;}for (int i = M - 1; i >= 0; --i) {for (int t = 1; t < T + 1; ++t) {if (t < mt[i]) {dp[t][i] = dp[t][i + 1];}else {dp[t][i] = max(mv[i] + dp[t - mt[i]][i + 1], dp[t][i + 1]);}}}cout << dp[T][0] << endl;return 0;
}

参考图：