采藥（01背包）

FJUT 2347

Problem Description

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

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

Input

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

Output

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

SampleInput

70 3

71 100

69 1

1 2

SampleOutput

3

經典的背包問題，dp解決。當然也可以暴力 暴力是萬能的 但會TLE。

首先開兩個數組 time【i】，weight【i】 采每種藥需要的時間和他的重量。。

然後對于每種藥 我們有兩個選擇，可以采也可以不采，前提是看采這個藥的時間是否小于等于剩餘時間 是的話在選擇，既然要最大值，肯定是要成本效益高的了。這樣的話我們定義一個二維數組dp【i】【j】 表示前i個藥花費j時間所放的最大重量。。

如果time【i】＞剩餘的時間 那麼dp【i】【j】就等于dp【i-1】【j】

那麼如果time【i】<=剩餘的時間，就可以選擇weight放或者不放，那麼怎麼判斷放不放呢

就是狀态轉移方程

dp【i】【j】=max（ dp【i-1】【j】， dp【i-1】【j-time【i】】+weight【i】） ）

将目前這個藥所需要花的時間減去 在加上目前藥的價值看是不是比不采目前藥的重量大，是就采，不是就不采。

最後的結果就是dp【藥的個數】【總共時間】

代碼如下

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dp[105][1005];
int main()
{
    ll w[1005],time[1005],i,j,t,m;
    cin>>t>>m;
    for(i=1;i<=m;i++)
        cin>>time[i]>>w[i];


    for(i=1;i<=m;i++)
    {
        for(j=0;j<=t;j++)
        {
            if(j<time[i])
                dp[i][j]=dp[i-1][j];
            else
            {
                dp[i][ j ]=max( dp[ i-1 ][ j ] ,  dp[i-1][j-time[i]]+w[i]  );
            }
        }
    }
    cout<<dp[m][t];
}
           

複雜度是O（n*m）。

這裡介紹一下 用一維數組dp的空間優化，dp【i】【j】是由dp【i-1】【j】得到而來的，是以我們可以把dp作為存重量的數組即可，而i每一次都進行疊代就行。

附上代碼

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t,m;
    cin>>t>>m;
    int dp[1005]={0},v[1005],w[1005],i,j;
    for(i=0;i<m;i++)
        cin>>w[i]>>v[i];

    for(i=0;i<m;i++)
    {
        for(j=t;j>=w[i];j--)
        ///這裡注意要逆序，因為狀态轉移方程dp【i】【j】是由dp【i-1】【j】得來的，如果順序的話
        ///會被覆寫，也就是會被選擇多次 就變成了完全背包了
            if(dp[j-w[i]]>=0) dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
    }
    cout<<dp[t];
}