1821: 入學(xué)考試（1261采藥）
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 32 Solved: 26
[Submit][Status][Web Board]
Description

辰辰是個(gè)天資聰穎的孩子，他的夢(mèng)想是成為世界上最偉大的醫(yī)師。為此，他想拜附近最有威望的醫(yī)師為師。醫(yī)師為了判斷他的資質(zhì)，給他出了一個(gè)難題。醫(yī)師把他帶到一個(gè)到處都是草藥的山洞里對(duì)他說：“孩子，這個(gè)山洞里有一些不同的草藥，采每一株都需要一些時(shí)間，每一株也有它自身的價(jià)值。我會(huì)給你一段時(shí)間，在這段時(shí)間里，你可以采到一些草藥。如果你是一個(gè)聰明的孩子，你應(yīng)該可以讓采到的草藥的總價(jià)值最大。”

如果你是辰辰，你能完成這個(gè)任務(wù)嗎？

輸入格式 　　第一行有兩個(gè)整數(shù)T（1 < = T < = 1000）和M（1 < = M < = 100），用一個(gè)空格隔開，T代表總共能夠用來采藥的時(shí)間，M代表山洞里的草藥的數(shù)目。接下來的M行每行包括兩個(gè)在1到100之間（包括1和100）的整數(shù)，分別表示采摘某株草藥的時(shí)間和這株草藥的價(jià)值。 輸出格式 　　包括一行，這一行只包含一個(gè)整數(shù)，表示在規(guī)定的時(shí)間內(nèi)，可以采到的草藥的最大總價(jià)值。 樣例輸入 70 3 71 100 69 1 1 2 樣例輸出 3 數(shù)據(jù)規(guī)模和約定 　　對(duì)于30%的數(shù)據(jù)，M < = 10； 　　對(duì)于全部的數(shù)據(jù)，M < = 100。

Input

第一行有兩個(gè)整數(shù)T（1 < = T < = 1000）和M（1 < = M < = 100），用一個(gè)空格隔開，T代表總共能夠用來采藥的時(shí)間，M代表山洞里的草藥的數(shù)目。接下來的M行每行包括兩個(gè)在1到100之間（包括1和100）的整數(shù)，分別表示采摘某株草藥的時(shí)間和這株草藥的價(jià)值。

Output

包括一行，這一行只包含一個(gè)整數(shù)，表示在規(guī)定的時(shí)間內(nèi)，可以采到的草藥的最大總價(jià)值。

Sample Input

70 3
71 100
69 1
1 2

Sample Output

3

HINT

Source
//1261和1821題目一樣，之前做1261空間復(fù)雜度沒做優(yōu)化~
Ac_code:
//現(xiàn)在寫的

#include <iostream> #include <string.h> #include <algorithm> using namespace std; int t[105],v[105],f[1002]; int main() {int T,M;while(cin>>T>>M){memset(f,0,sizeof(f));for(int i = 0; i < M; i++){cin>>t[i]>>v[i];}for(int i = 0; i < M; i++){for(int j = T; j >= t[i]; j--){f[j] = max(f[j],f[j-t[i]]+v[i]);}}cout<<f[T]<<endl;}return 0; }

//之前用C寫的

#include <stdio.h> #include <string.h> #define Max(x,y) x>y?(x):(y) int f[101][1001], t[101],v[101]; int main() {int T,M;while(~scanf("%d%d",&T,&M)){memset(f,0,sizeof(f));memset(t,0,sizeof(t));memset(v,0,sizeof(v));for(int i = 1; i <= M; i++){scanf("%d%d",&t[i],&v[i]);}for(int i = 1; i <= M; i++){for(int j = 1; j <= T; j++){if(t[i] <= j){f[i][j] = Max(f[i-1][j],f[i-1][j-t[i]]+v[i]);}else f[i][j] = f[i-1][j];}}printf("%d\n",f[M][T]);}return 0; } 與50位技術(shù)專家面對(duì)面20年技術(shù)見證，附贈(zèng)技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的1821: 入学考试（1261采药）01背包的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。