----來自退役三年的OIer對自己當年的記憶
先來一個經(jīng)典問題
P1048 [NOIP2005 普及組] 采藥 - 洛谷 | 計算機科學教育新生態(tài) (luogu.com.cn)
沒有什么想法......
不妨先假設：
假設我現(xiàn)在覺得要不要某一個草藥
那我肯定這樣思考：比較要這個草藥能獲得的收益與不要這個草藥能獲得的收益
假如說我從第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的前提下
依照習慣，一般循環(huán)從1寫到n
故可以改變形式為

f(n,t)=max(f(n-1,t) , 利潤n+f(n-1,t-tn))

可用二維數(shù)組實現(xiàn)，即為動態(tài)規(guī)劃的最簡易形式

代碼如下：
#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數(shù)量 

    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;
}