fjutacm 2347 采藥 背包dp

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

Hint:對于30%的資料，M <= 10；

對于全部的資料，M <= 100。

這是我背包dp的入門題，是以我決定第一篇背包dp直接寫它的題解。我相信一個算法知識點一定要直接落實到實際問題的解決上，才有可能讓人真正了解并學會使用，不扯那麼多理論，直接分析題目。

所謂背包，就是給定一定容量T，有多個物品，每個物品需要t的容量，并具有v的價值，問怎麼取，能在不超背包總容量的情況下，拿到總價值最多的東西。

題目中，背包的容量就是師傅給定的總時間T。而背包dp的算法基礎，就是我們開一個基礎大小為T的數組dp，然後我們維護這一個數組的每一個位置i，也就是0~T這一段時間内每一個時間點的最優解。也就是說，我們要想辦法保證，每一個時間點都儲存着，有這麼多時間的情況下，我們所能拿到的最高總價值的東西。

比如在時間點i，存的就應該是我們還剩時間i的時候所能得到的最優解。這樣，我們一番動态規劃後，dp[T]的值代表我們有T的時間的時候所能得到的最優解，即是我們所要求的答案。至于為什麼在每個時間點i我們都要維護當下最優解，結合代碼會更好了解，我們在注釋裡繼續分析。

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <math.h>
#include <iostream>
const int MAX=1e6;
using namespace std;
int t[105], v[105], dp[1005];/// dp[]的大小一定要開到總時間那麼大

int main()
{
  int T, M;
  cin >> T >> M;
  for (int i=1; i<=M; i++)
    cin >> t[i] >> v[i];/// 花費t[i]能獲得相應的價值v[i]
  for (int i=1; i<=M; i++)/// 每一株藥草都試一遍，看的是“是否要取”
  {
    for (int j=T; j>=t[i]; j--)/// 從後往前周遊，我們就能保證在不同的時間點，
///同一株藥草至多被取了一次，以維持那個時間點的最優選擇。
///如果從前往後周遊，稍微模拟一下我們就會知道，有可能出現一株草藥被取多次的
///情況，并且連被取了幾次都不清楚，而這題每種草藥就獨一株
      dp[j] = max(dp[j], dp[j-t[i]]+v[i]);/// 這裡就是維護最優解，二選一，一個
///是之前循環留下的暫時最優的（或初始的）狀态，一個是取目前時間總量j，預留出
///草藥i所需時間t[i]時的目前最優解dp[j-t[i]]，補上藥草i的價值v[i]。然後我們要
///最多的價值，是以在dp[j]和dp[j-t[i]]+v[i]之間max一下取較大，這就完成了時間
///點j的最優解維護
  }
           

這裡我插一組案例和它的整個運作過程，幫助我們更好地模拟背包dp基本的流程。

10 5

1 2

3 2

2 1

5 4

4 2

t: 1 3 2 5 4

v: 2 2 1 4 2

j: 0 1 2 3 4 5 6 7 8 9 10

i=1開始前: 0 0 0 0 0 0 0 0 0 0 0

i=1結束後: 0 2 2 2 2 2 2 2 2 2 2

i=2結束後: 0 2 2 2 4 4 4 4 4 4 4

i=3結束後: 0 2 2 3 4 4 5 5 5 5 5

i=4結束後: 0 2 2 3 4 4 6 6 7 8 8

i=5結束後: 0 2 2 3 4 4 6 6 7 8 8

最優解自然就是8，然後我們代碼接上面的

/// 因為這一題，每一層狀态都隻與上一層的狀态有關，也就是考慮完一株藥草之後
  ///我們就可以直接開始下一株，是以是一維的簡單問題，我們就隻開了一個一維的
  ///dp數組進行滾動更新。
  /// 真的要寫的話，還有另外一種二維dp數組的寫法，開dp[藥草株數][總時長]，從
  ///前開始更新從後開始更新都一樣，在dp[k-1][j]和dp[k-1][j-t[i]]+v[i]中選max賦
  ///給dp[k][j]。
  cout << dp[T];/// 最終，“有T時間情況下能拿到的最多的價值”即我們要的最優解。
  return 0;
}
           

寫了這麼多，主要還是希望自己以後想撿回來的時候能秒懂。學習筆記，說到底還是寫給自己看的，是以寫得可能不是很好，盡量了解。