1103: 开心的金明

解题思路:

背包问题，解法和采药一模一样！

传送面板已上线，我们的行动会更加快捷：https://blog.dotcpp.com/a/85195

注意事项:

动态规划的真谛就是状态转移方程！

参考代码:

// 题目 1103: 开心的金明
#include <iostream>
#include <cstring>

using namespace std;

int main() {
	int N = 0; // 总钱数
	int m = 0; // 希望购买的物品个数
	cin >> N >> m;

	// 异常处理
	if (N >= 30000 || m >= 25) {
		cerr << "DATA ERROR" << endl;
		return -1;
	}

	// 读输入
	int value[m + 1]; // 每件物品的价格
	int worth[m + 1]; // 每件物品的重要度
	int sum[m + 1];   // 每件物品的总价值
	memset(value, 0, m + 1);
	memset(worth, 0, m + 1);
	memset(sum, 0, m + 1);
	for (int i = 1; i < m + 1; i++) {
		cin >> value[i] >> worth[i];
		sum[i] = value[i] * worth[i];
	}

	int res[N + 1][m + 1]; // 存储结果（最优解）
	memset(res, 0, sizeof(res));
	for (int i = 1; i < N + 1; i++) {
		for (int j = 1; j < m + 1; j++) {
			if (i < value[j]) {
				res[i][j] = res[i][j - 1]; // 买不起
			} else {
				// 买得起，比较买和不买的总价值
				res[i][j] = max(res[i][j - 1], res[i - value[j]][j - 1] + sum[j]);
			}
		}
	}
	cout << res[N][m] << endl; // 钱数为N并考虑m个物品时的最优解即为答案
	return 0;
}