題目描述
辰辰是個(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à)值。
解題思路
本題是典型的動(dòng)態(tài)規(guī)則毅整，我的思路是：每輸入一種草藥就計(jì)算出當(dāng)前在規(guī)定時(shí)間內(nèi)能采到草藥的最大價(jià)值趣兄。
使用dp[]數(shù)組來(lái)保存某一個(gè)時(shí)間點(diǎn)上的采到草藥的最大價(jià)值。所以輸入71 100 時(shí)dp數(shù)組為
當(dāng)輸入第二組數(shù)據(jù) 69 1 時(shí)
當(dāng)輸入第三組數(shù)據(jù) 1 2 時(shí)
此時(shí)最優(yōu)解是dp[70] 是3悼嫉。
代碼如下：
#include<stdio.h>
int dp[1001]={0}; ? ?//保存時(shí)間T時(shí)的采藥最大價(jià)值
int main(){
? ? ? int totalTime,totalNumber; ?//總時(shí)間和總的草藥個(gè)數(shù)艇潭。
? ? ? scanf("%d%d",&totalTime,&totalNumber);
? ? ? int time,value;
? ? ? for(int i = 0 ; i <totalNumber; i++)
? ? ? {
? ? ? ? ? ?scanf("%d%d",&time,&value);
? ? ? ? ? for(int j = totalTime; j>=time ; j--)
? ? ? ? ? {
? ? ? ? ? ? ? if(dp[j] < dp[j - time] + value){ //如果當(dāng)前值加上剩下的時(shí)間最大值大于j時(shí)間的最大值
? ? ? ? ? ? ? ? dp[j] = dp[j - time] +value;
? ? ? ? ? ? ? ?}
? ? ? ? }
? ? ? }
? ? ? printf("%d\n",dp[totalTime]);
? ? ? return 0;
}
