例题12.7 点菜问题（北京大学复试）

例题12.7 点菜问题（北京大学复试）链接

关键字：0-1背包、动态规划

算法：设计dp[i][j] 用来存储将物品i放入背包中后可以达到的最大的价值j

分两种情况：

CASE1: 当前背包没有足够空间，无法将商品 i 放入其中，此时的转移方程即为dp[i][j] = dp[i-1][j]

CASE2: 当前背包的空间充足，可以放入当前的商品i，这时候需要考虑两种情况，即将商品i放入其中取得的最大价值和不将商品i放入取得的最大价值中最大的那一个，此时转移方程为dp[i][j] = max(dp[i-1][j], dp[i-1][j - weight[i]] + value[i])

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

int main() {
	int m, n;
	while (cin >> m && cin >> n) {
		vector<int> price(n+1,0);
		vector<int> value(n+1,0);
		//1.输入数据
		for (int i = 1; i <= n; i++) {
			cin >> price[i];
			cin >> value[i];
		}
		//2.根据转移方程计算最大价值
		vector<vector<int>> dp(n + 1, vector<int>(m + 1,0));
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				//2.1如果该商品价格过高，剩余的钱无法支付，则i商品不放入背包中
				if (j - price[i] < 0) {
					dp[i][j] = dp[i - 1][j];
				}
				//2.2如果该商品可以放入背包，则选择在这两种情况中判断即 max(不放入背包的最大价值，放入背包的最大价值)
				else {
					dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - price[i] ]+ value[i]);
				}
			}
		}
		cout << dp[n][m] << endl;
	}
	return 0;
}