NOIP2005普及組第3題 采藥
時間限制:?1 Sec??內存限制:?128 MB提交:?50??解決:?23
[提交][狀態][討論版][命題人:外部導入]
題目描述
辰辰是個天資聰穎的孩子，他的夢想是成為世界上最偉大的醫師。為此，他想拜附近最有威望的醫師為師。醫師為了判斷他的資質，給他出了一個難題。醫師把他帶到一個到處都是草藥的山洞里對他說：“孩子，這個山洞里有一些不同的草藥，采每一株都需要一些時間，每一株也有它自身的價值。我會給你一段時間，在這段時間里，你可以采到一些草藥。如果你是一個聰明的孩子，你應該可以讓采到的草藥的總價值最大。”?
?
如果你是辰辰，你能完成這個任務嗎？
輸入
第一行有兩個整數T（1?<=?T?<=?1000）和M（1?<=?M?<=?100），用一個空格隔開，T代表總共能夠用來采藥的時間，M代表山洞里的草藥的數目。接下來的M行每行包括兩個在1到100之間（包括1和100）的整數，分別表示采摘某株草藥的時間和這株草藥的價值。
輸出
包括一行，這一行只包含一個整數，表示在規定的時間內，可以采到的草藥的最大總價值。
?
?
【數據規模】
?
?
?
對于30%的數據，M?<=?10；
?
對于全部的數據，M?<=?100。
?
?
樣例輸入
70 3
71 100
69 1
1 2 樣例輸出
3
題目的要求是用有限的時間獲取價值盡可能高的草藥，所以可以用01背包來做。
可以假設采藥時的最優解是在時間T內i棵，用c(i,T)表示，此時這個解要么包含i這棵草藥，要么不包含，假設采這顆草藥的時間為T1，價值為V,如果包含，這個最優解變成了c(i-1,T-T1)+V，如果不包含，這個最優解變成了c(i-1,T)，這時只要判斷c(i-1,T-T1)+V和c(i-1,T)哪個價值更大，哪個就是最優解，即c(i,T)=max(c(i-1,T-T1)+V,c(i-1,T))。
現在令第j個草藥的價值為v[j]，采這個草藥的時間為ti[j]，i時的價值為h[i],則有h[i]=max(h[i-1],h[i-ti[j]]+v[j])。而h[0]為0，我們就得到了最優解的遞推公式。代碼如下:
?
#include <iostream> #include <cstring> #include <string> #include <algorithm> using namespace std; int dp[1005]; int v[105],w[105]; int main() {int t,n;int i;cin>>t>>n;for(i=1;i<=n;i++)cin>>w[i]>>v[i];memset(dp,0,sizeof(0));for(i=1;i<=n;i++){for(int j=t;j>=w[i];j--){dp[j]=max(dp[j],dp[j-w[i]]+v[i]);}}cout<<dp[t];return 0; }
?
?
