P1048 采藥-----典型的01背包動态規劃問題

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

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

輸入格式

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

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

輸出格式

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

輸入輸出樣例

輸入 #1

70 3

71 100

69 1

1 2

輸出 #1

3

代碼如下：

#include <iostream>
#include <algorithm>
using namespace std;

int dp[105][1005]; //一維表示可以裝入背包的物品數量，二維表示背包的剩餘空間
int w[105], v[105]; //記錄物品的品質和價值

int main()
{
	int con, n;
	cin >> con >> n; //輸入背包的最大容量和物品的數量
	for (int i = 1; i <= n; i++)
		cin >> w[i] >> v[i]; 

	for(int i = 1; i <= n; i++) //這裡的二重循環相當于枚舉，嘗試将每一種物品，放入每一個可能的容量中，再依據狀态方程計算出最優解
		for (int j = con; j >= 0; j--) //周遊對應目前物品的所有容量的背包，嘗試放入
		{
			if (j >= w[i]) //當背包的空間大于目前貨物的重量的時候（清理之後可以裝下）
				dp[i][j] = max(dp[i - 1][j - w[i]] + v[i], dp[i - 1][j]);
			    //比較将背包清理出部分空間，再放入目前物品的總價值，和未放入物品時該背包的總價值（是否要裝）
			else //即使将背包清空也無法裝下目前物品 （跟本裝不下，那就算了...）
				dp[i][j] = dp[i - 1][j]; //處于目前貨物周遊層的背包的總價值和上一層背包的宗廟和價值一樣。
		}1

	cout << dp[n][con]; //輸出具有最大空間，并且完成了全部貨物周遊的背包的價值
	return 0;
}