----来自退役三年的OIer对自己当年的记忆
先来一个经典问题
P1048 [NOIP2005 普及组] 采药 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
没有什么想法......
不妨先假设：
假设我现在觉得要不要某一个草药
那我肯定这样思考：比较要这个草药能获得的收益与不要这个草药能获得的收益
假如说我从第1株草药开始选择，一共有 T 的时间
那么我应当考虑第 2-M 株用 T 时间能获得的最大收益 与 第1株的利润+第 2-M 株用 T-t1 时间能获得的最大收益
即
f(1-n,t)=max( f(2-n,t) , 利润1+f(2-n,t-t1) )
显然，这一切建立在T>=t1的前提下
依照习惯，一般循环从1写到n
故可以改变形式为
f(n,t)=max(f(n-1,t) , 利润n+f(n-1,t-tn))
可用二维数组实现，即为动态规划的最简易形式
代码如下：
#include<iostream>
using namespace std;
int P[101]={0},V[101]={0},s[101][1001]={0};
int main()
{
int m,n;//P价值，V时间
cin>>m>>n;//m总时间，n数量
for(int i=1;i<=n;i++)cin>>V[i]>>P[i];
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(V[i]>j)s[i][j]=s[i-1][j];
else s[i][j]=max(s[i-1][j],P[i]+s[i-1][j-V[i]]);
}
}
cout<<s[n][m];
return 0;
}
