洛谷P1048 采藥

題目OJ位址

https://www.luogu.org/problemnew/show/P1048

https://vijos.org/p/1104

題目描述

辰辰是個天資聰穎的孩子，他的夢想是成為世界上最偉大的醫師。為此，他想拜附近最有威望的醫師為師。

醫師為了判斷他的資質，給他出了一個難題。醫師把他帶到一個到處都是草藥的山洞裡對他說：“孩子，

這個山洞裡有一些不同的草藥，采每一株都需要一些時間，每一株也有它自身的價值。我會給你一段時間，

在這段時間裡，你可以采到一些草藥。如果你是一個聰明的孩子，你應該可以讓采到的草藥的總價值最大。”

如果你是辰辰，你能完成這個任務嗎？

輸入輸出格式

輸入格式：

第一行有2個整數T(1≤T≤1000)和M(1≤M≤100)，用一個空格隔開，T代表總共能夠用來采藥的時間，

M代表山洞裡的草藥的數目。

接下來的M行每行包括兩個在1到100之間（包括1和100）的整數，分别表示采摘某株草藥的時間和這株草藥的價值。

輸出格式：

1個整數，表示在規定的時間内可以采到的草藥的最大總價值。

輸入輸出樣例

輸入樣例#1：

70 3

71 100

69 1

1 2

輸出樣例#1：

3

說明

對于30%的資料，M≤10；

對于全部的資料，M≤100。

算法分析：

在這裡，我們将M種草藥編号1~M，定義dp[i][j]為“從前i種草藥選擇若幹種去采摘，花費時間不超過j，所能得到的最大價值”。那麼，狀态轉移方程如下：

dp[i][j]= max(   dp[i-1][j] ,  dp[i-1][j-w[i] ]+v[i]  )

意思是：

在考慮從前i種草藥選擇若幹種去采摘時有兩種政策：

（一）不選第i種草藥，那麼應該有dp[i][j]=dp[i-1][j]

（二）選擇第i種草藥，那麼dp[i][j]=dp[i-1][j-w[i]]+v[i]

1 #include <stdio.h>
 2 int dp[101][1001]={0},T,M,w[1001]={0},v[1001]={0};
 3 int max2(int a,int b)
 4 {  return a>b?a:b; }
 5 void fun()
 6 {
 7     int i,j;
 8     for(i=1;i<=M;i++)
 9     {
10         for(j=0;j<=T;j++)
11         {
12             if(j>=w[i]) dp[i][j]=max2(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
13             else dp[i][j]=dp[i-1][j];
14         }
15     }
16 }
17 int main()
18 {
19     int i;
20 
21     scanf("%d%d",&T,&M);
22     for(i=1;i<=M;i++)
23         scanf("%d%d",&w[i],&v[i]);
24     fun();
25     printf("%d\n",dp[M][T]);
26     return 0;
27 }