一、解题思路: 问题分析:给定背包容量T和M个物品(草药),每个物品有采摘时间t和价值v,求在限定时间内能获得的**价值。 状态定义:定义dp[j]表示前i个物品在时间j限制下的**价值。 若当前物品时间超过剩余时间:dp[j] = dp[i-1][j] 否则:dp[j] = max(dp[i-1][j], dp[i-1][j-t] + v)。 优化:使用滚动数组将空间复杂度从O(NV)降为O(V),需逆序遍历时间。 二、代码实现:
- #include<bits/stdC++.h>
- using namespace std;
- int main() {
- int T, M; // 总时间和草药数量
- cin >> T >> M;
- int t[105], v[105]; // 时间和价值数组
- int dp[1005] = {0}; // 滚动数组优化
- for(int i = 1; i <= M; i++)
- cin >> t[i] >> v[i];
- // 动态规划核心
- for(int i = 1; i <= M; i++) {
- for(int j = T; j >= t[i]; j--) { // 逆序遍历防止重复计算
- dp[j] = max(dp[j], dp[j - t[i]] + v[i]);
- }
- }
- cout << dp[T]; // 输出**价值
- return 0;
- }
复制代码
代码通过滚动数组优化空间,逆序遍历确保每个物品只被计算一次,时间复杂度O(MT),适用于题目约束范围。
|