題目描述
辰辰是個天資聰穎的孩子，他的夢想是成為世界上最偉大的醫(yī)師。為此，他想拜附近最有威望的醫(yī)師為師。醫(yī)師為了判斷他的資質(zhì)，給他出了一個難題。醫(yī)師把他帶到一個到處都是草藥的山洞里對他說：“孩子，這個山洞里有一些不同的草藥，采每一株都需要一些時間，每一株也有它自身的價值。我會給你一段時間，在這段時間里，你可以采到一些草藥。如果你是一個聰明的孩子，你應(yīng)該可以讓采到的草藥的總價值最大?！?/p>
如果你是辰辰，你能完成這個任務(wù)嗎？
輸入格式
輸入的第一行有兩個整數(shù)T（1 <= T <= 1000）和M（1 <= M <= 100），用一個空格隔開，T代表總共能夠用來采藥的時間，M代表山洞里的草藥的數(shù)目。接下來的M行每行包括兩個在1到100之間（包括1和100）的整數(shù)，分別表示采摘某株草藥的時間和這株草藥的價值。
輸出格式
輸出包括一行，這一行只包含一個整數(shù)，表示在規(guī)定的時間內(nèi)，可以采到的草藥的最大總價值。
解題思路
本題是典型的動態(tài)規(guī)則，我的思路是：每輸入一種草藥就計算出當(dāng)前在規(guī)定時間內(nèi)能采到草藥的最大價值。
使用dp[]數(shù)組來保存某一個時間點上的采到草藥的最大價值。所以輸入71 100 時dp數(shù)組為
當(dāng)輸入第二組數(shù)據(jù) 69 1 時
當(dāng)輸入第三組數(shù)據(jù) 1 2 時
此時最優(yōu)解是dp[70] 是3。
代碼如下：
#include<stdio.h>
int dp[1001]={0}; ? ?//保存時間T時的采藥最大價值
int main(){
? ? ? int totalTime,totalNumber; ?//總時間和總的草藥個數(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)前值加上剩下的時間最大值大于j時間的最大值
? ? ? ? ? ? ? ? dp[j] = dp[j - time] +value;
? ? ? ? ? ? ? ?}
? ? ? ? }
? ? ? }
? ? ? printf("%d\n",dp[totalTime]);
? ? ? return 0;
}
