1100: 采药（背包问题）

解题思路:

属于背包问题，用动态规划的思想求解。

核心计算公式：t时间内考虑m个草药并且选择“采”的价值，计算公式为：（t - 第m个草药的耗时）时间内考虑（m - 1）个草药的最有解 + 第m个草药的价值。

可能说的很难理解，建议看源码。

注意事项:

（1）数组归零最好用memset()，我一开始用res[T + 1][M + 1] = { 0 }，结果debug时发现res[0][3] = 32767，很神奇，以后老老实实用memset()了。

（2）为了便于理解数组的大小设定为T + 1和M + 1，注意边界。

参考代码:

// 题目 1100: 采药
#include <iostream>
#include <cstring>

using namespace std;

int main() {

	int T = 0; // 规定时间
	int M = 0; // 草药数目
	cin >> T >> M;

	// 用i表示第i个草药，便于理解
	int time[M + 1] = { 0 };  // 第i个草药的采集时间
	int value[M + 1] = { 0 }; // 第i个草药的价值
	for (int i = 1; i < M + 1; i++) {
		cin >> time[i] >> value[i];
	}

	int res[T + 1][M + 1]; // 最优解，表示在时间T内考虑前M个物品时的最大价值
	memset(res, 0, sizeof(res)); // 数组归零的写法要用memset()，用res[][] = { 0 }好像不行

	for (int i = 1; i < T + 1; i++) {
		for (int j = 1; j < M + 1; j++) {
			if (i < time[j]) {
				res[i][j] = res[i][j - 1]; // 第i个草药没法采
			} else {
				// 第i个草药可以采，比较采和不采的价值，注意前者的计算公式
				res[i][j] = max(res[i][j - 1], res[i - time[j]][j - 1] + value[j]);
			}
		}
	}

	cout << res[T][M] << endl; // 输出在T时间内考虑M个草药的最优解
	return 0;
}