描述
辰辰是個(gè)天資聰穎的孩子伞插，他的夢(mèng)想是成為世界上最偉大的醫(yī)師。為此艇纺，他想拜附近最有威望的醫(yī)師為師怎静。醫(yī)師為了判斷他的資質(zhì)，給他出了一個(gè)難題黔衡。醫(yī)師把他帶到一個(gè)到處都是草藥的山洞里對(duì)他說(shuō)：“孩子蚓聘，這個(gè)山洞里有一些不同的草藥，采每一株都需要一些時(shí)間盟劫，每一株也有它自身的價(jià)值夜牡。我會(huì)給你一段時(shí)間，在這段時(shí)間里侣签，你可以采到一些草藥塘装。如果你是一個(gè)聰明的孩子，你應(yīng)該可以讓采到的草藥的總價(jià)值最大影所”碾龋”
如果你是辰辰，你能完成這個(gè)任務(wù)嗎猴娩？
格式
輸入格式
輸入的第一行有兩個(gè)整數(shù)T（1 <= T <= 1000）和M（1 <= M <= 100）阴幌，用一個(gè)空格隔開(kāi)，T代表總共能夠用來(lái)采藥的時(shí)間卷中，M代表山洞里的草藥的數(shù)目矛双。接下來(lái)的M行每行包括兩個(gè)在1到100之間（包括1和100）的整數(shù)，分別表示采摘某株草藥的時(shí)間和這株草藥的價(jià)值蟆豫。
輸出格式
輸出包括一行议忽，這一行只包含一個(gè)整數(shù)，表示在規(guī)定的時(shí)間內(nèi)十减，可以采到的草藥的最大總價(jià)值徙瓶。
樣例1
輸入樣例1
70 3
71 100
69 1
1 2
輸出樣例1
3
代碼實(shí)現(xiàn)
#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;
int main() {
/*
T-->總共可以用來(lái)采藥的時(shí)間
M-->山洞里草藥的數(shù)目
v-->采摘某株草藥的時(shí)間
w-->該株草藥的價(jià)值
*/
int dp[1001]={0};
int T,M,v,w;
cin >> T >> M;
for(int i = 0; i < M; i++ ){
cin >> v >> w;
for(int j = T; j >= v; j --){
dp[j] = max(dp[j],dp[j-v]+w);
}
}
cout << dp[T];
return 0;
}
