ARTICLE · 1092479
信奥赛真题题解[NOIP 2005 普及组] 第三题采药
信奥赛真题题解[NOIP 2005 普及组] 第三题采药
本题是纯动态规划01背包问题，可以直接套模板使用。 
状态：dp[j]表示背包容量为j时能够获得的最大价值 转移方程：dp[j]=max(dp[j] , dp[j-t[i-1]]+v[i-1]) 使用了一维数组优化，代码如下：
商丘地区可带孩子免费体验一次编程试听课
[NOIP 2005 普及组] 采药
NOIP 2005 普及组第三题
#include<iostream>using namespace std;int T, M;int v[105], t[105];int dp[1005];intmain(){cin>>T>>M;for(int i=0; i<M; i++) {//输入每个草药的时间和价值cin>>t[i]>>v[i];}for(int i=1; i<=M; i++)//遍利每一个草药for(int j=T; j>= t[i-1]; j--) //保证每个草药只取一次，j值从大到小dp[j]=max(dp[j], dp[j-t[i-1]]+v[i-1]); //j逆序可确保计算dp[j]时dp[j-t[i-1]]的值仍是上一轮的//从而防止同一物品被重复计算cout<<dp[T];return 0;}