NOIP2005 普及组 洛谷P1408 背包问题的空间优化技巧与实战应用

题目重解

想象你是一名药师，有t分钟在山上采集m种草药。每种草药需要time分钟采集，价值为num。这就像考试时分配时间做题，要选择收益最大的题目组合。题目要求计算在规定时间内能获得的最大草药价值。

解题思路

代码实现分为三个阶段：

初始化阶段：创建dp数组表示各时间段的最优解，初始值为0（未采集任何草药的状态）

动态转移阶段：对每种草药逆序更新dp数组，确保每种草药只被计算一次。状态转移方程dp[j] = max(保持原状, 采集当前草药)体现了取舍决策

输出结果：直接读取dp[t]即为时间上限下的最优解

代码注释版

#include<iostream>
using namespace std;
int main()
{
    int t,m;  // 总时间t分钟，草药种类m
    cin>>t>>m;
    
    int* dp=new int[t+1]; // dp数组：dp[j]表示j分钟内的最大价值
    int time,num;  // 当前草药的采集时间和价值
    
    for(int i=0;i<m;i++){  // 遍历每种草药
        cin>>time>>num;
        // 逆序更新防止重复采集
        for(int j=t;j>=time;j--)  
            dp[j]=max(dp[j], dp[j-time]+num); // 经典状态转移
    }
    cout<<dp[t];  // 输出最终结果
    
    return 0;
}