洛谷P1048 經典01背包問題 [NOIP2005 普及組] 采藥 動态規劃 dp

題目描述

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

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

輸入格式

第一行有 2 個整數 T（1≤T≤1000）和 M（M≤100），用一個空格隔開，T 代表總共能夠用來采藥的時間，M 代表山洞裡的草藥的數目。

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

輸出格式

輸出在規定的時間内可以采到的草藥的最大總價值。

輸入輸出樣例

輸入 

70 3
71 100
69 1
1 2
           

輸出 

3
           

說明/提示

【資料範圍】

• 對于 30\%30% 的資料M≤10；
• 對于全部的資料M≤100。

【題目來源】

NOIP 2005 普及組第三題

經典的01背包問題，一般這種問題都可以按照以下套模闆

代碼區

#include<iostream>
#include<cstdio>
#include<string.h>
#include<cmath>
using namespace std;
int T,m;
int t[1005],v[1005],dp[1005];//稍微定義大一點準沒錯，嘿嘿
int main()
{
    memset(t,0,sizeof(t));//數組初始化
    memset(v,0,sizeof(v));//數組初始化
    memset(dp,0,sizeof(dp));//數組初始化
    cin >> T >> m;//輸入總時間和草藥種類數
    for(int i=1;i<=m;++i)
    {
        cin >> t[i] >> v[i];//依次輸入所需時間和價值
    }
    for(int i=1;i<=m;++i)//對于每一種草藥開始查找最大dp值
    {
        for(int j=T;j>=t[i];--j)//從滿背包開始循環，直到裝不下為止
        {
            dp[j]=max(dp[j],dp[j-t[i]]+v[i]);
            //兩種選擇，前者是不取該草藥，後者是取，然後減去重量加上價值
        }
    }
    cout << dp[T] << endl;//輸出背包容量為T時的最大價值
    return 0;
}
           

新手上路，有錯請指正