動态規劃--采藥（01背包）

總時間限制: 1000ms

記憶體限制: 65536kB

描述

辰辰是個很有潛能、天資聰穎的孩子，他的夢想是稱為世界上最偉大的醫師。為此，他想拜附近最有威望的醫師為師。醫師為了判斷他的資質，給他出了一個難題。醫師把他帶到個到處都是草藥的山洞裡對他說：“孩子，這個山洞裡有一些不同的草藥，采每一株都需要一些時間，每一株也有它自身的價值。我會給你一段時間，在這段時間裡，你可以采到一些草藥。如果你是一個聰明的孩子，你應該可以讓采到的草藥的總價值最大。”

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

輸入

輸入的第一行有兩個整數T（1 <= T <= 1000）和M（1 <= M <= 100），T代表總共能夠用來采藥的時間，M代表山洞裡的草藥的數目。接下來的M行每行包括兩個在1到100之間（包括1和100）的的整數，分别表示采摘某株草藥的時間和這株草藥的價值。

輸出

輸出隻包括一行，這一行隻包含一個整數，表示在規定的時間内，可以采到的草藥的最大總價值。

樣例輸入

70 3

71 100

69 1

1 2

樣例輸出

3

題目大概：

在n的限定時間之内，采到最大價值的草藥。藥草數固定且唯一。

思路：

這是一個背包類的dp題。

子問題：花一定時間 采一株藥草。

狀态：a[i][j] i表示第i株藥草，j表示花費的總時間。a[i]時間  b[j]價值

   當然a[i][j]也可以用一維數組h[j]表示。表示的意思相同，隻是省略了一部分，節省了一部分空間。

狀态轉移方程：第i株草藥有兩種情況  1。。不會被采，則價值a[i][j]=a[i-1][j]或者h[j]=h[j]..注意此時前後兩個h[j]意義不同，觀察前面的式子就可以得到意思。

                                                             2.。被采 則價值a[i][j]=a[i-1][j-a[i]]或h[j]=h[j-a[i]].。

 但前提是在時間j大于a[i]的情況下。

感想;

代碼;

#include<bits/stdc++.h>
using namespace std;
int a[101],b[101],h[1001];

int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>a[i]>>b[i];
    }
    for(int i=1;i<=m;i++)
    {
        for(int j=n;j>=a[i];j--)
        {
            h[j]=max(h[j],h[j-a[i]]+b[i]);
        }
    }
    cout<<h[n];
    return 0;
}