Vijos P1104 采藥 動态規劃

描述

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

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

格式

輸入格式

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

輸出格式

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

一，分析

很明顯，這是一個非常簡單的01背包問題，讓我們從決策出發來分析這個問題，與我們之前的動态規劃一樣，我們的整體的問題就是一系列決策構成的，隻要把每一個決策出來好了，我們的問題就非常容易解決了，對于決策，我們要清楚兩個問題，第一個，我們要先清楚我們作的決策到底是什麼，對于01背包問題決策很簡單就是是否将ai放進背包中，最長不下降子序列的決策是ai要選擇那一個序列加入，對于maxsum來說，決策就是ai是否加入之前的隊列，還是建立一個隊列，第二個問題就是我們進行決策的政策，動态規劃特别精妙的地方就在于，他對于狀态清晰的定義，使得我們對于決策變的清晰和簡單。

那麼讓我們回到01倍包，我們的決策是“是否将第i個物品放入背包中”，而我們注意到，不像前幾個問題一樣，背包問題還有w［i］和c［i］這個次元，我們在進行狀态定義的時候如果不把這幾個問題考慮在内，那麼我們不可能明智的做出決策，那麼考慮怎麼把這幾個要素融入到我們定義的狀态當中呢？首先考慮w即價值這個要素，他在狀态定義中應該處于的是“目的”或者說狀态本身，因為我們的目的就是求出來最大的w，是以，我們分析，我們最終定義出來的狀态大緻應該是這樣的 f［i］是“前i個物品的最大w”，現在隻剩下c這個要素需要考慮，因為我們首次引入兩個要素座位參數，那麼我們可以類比i的引入方式，即我們最終定義的狀态f［i］［c］是“前i個物品在容量為c的空間内的最大容量”。

好了，定義好了一個清晰可靠的狀态，讓我們再回到，決策的第二個問題，我們需要确定作出決策的政策，有了狀态這個強有力的武器的我們不難找到這個政策即“使得f［i］［c］”最大，然而這時，我們發現這裡面還有一個c這個要素要考慮，那麼我們就要思考，在我們作出決策的過程中c到底是什麼呢？我們再回頭看看f［i］［c］即“前i個物品在容量為c的空間内的最大容量”，那麼我們在第i階段的狀态就應該有cmax個，根據我們在上面列出來的政策即“使得f［i］［c］最大“，我們不難列出狀态轉移方程f[i][c]=max{f[i-1][c],f[i-1][c-c[i]]}

<pre name="code" class="cpp">//
//  main.cpp
//  p1104采藥
//
//  Created by 張嘉韬 on 16/1/10.
//  Copyright © 2016年 張嘉韬. All rights reserved.
//

#include <iostream>
#include <cstdio>
using namespace std;
    int f[500][10000];
int max(int a,int b)
{
    if(a>b) return a;
    else return b;
}
int main(int argc, const char * argv[]) {
   //freopen("/Users/zhangjiatao/Desktop/input.txt","r",stdin);

    int t,n,w[10000],c[10000];
    cin>>t>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>c[i]>>w[i];
        f[i][0]=0;
    }
    for(int j=1;j<=t;j++)
    {
        if(j<c[1]) f[1][j]=0;
        else f[1][j]=w[1];
    }
    for(int i=2;i<=n;i++)
    {
        for(int j=1;j<=t;j++)
        {
            if(j<c[i]) f[i][j]=f[i-1][j];
            else f[i][j]=max(f[i-1][j],f[i-1][j-c[i]]+w[i]);
        }
    }
//    for(int i=1;i<=n;i++)
//    {
//        for(int j=1;j<=t;j++)
//        {
//            cout<<f[i][j]<<" ";
//        }
//        cout<<endl;
//    }
    cout<<f[n][t]<<endl;
    return 0;
}