题解 | 点菜问题

0-1背包问题：

背包：有一定体积/重量限制

物品：只能选择一次，放入背包/不放入背包；物品有双重属性：比如体积/重量和价值

目标函数：在满足容量约束的前提下，使得背包内物品的总价值最大化

动态规划解题：

最优解：大背包的最优解包含了小背包的最优解

子问题有重叠：（用递归会冗余）记录状态避免重复递归计算

#include <stdio.h>
#include <algorithm>
#include <vector>
#include<cstring>
using namespace std;

int main() {
	int C, N;//C总额，N种菜
	while (scanf("%d%d", &C, &N) != EOF) {
		int p[101];//价格
		int v[101];//评分
		for (int i = 1; i <= N; i++) {
			scanf("%d%d", &p[i], &v[i]);
		}
		int dp[1001][102];//dp[i][j]:总额剩余为i，有j种菜品可选时的最大评分和
		memset(dp, 0, sizeof(dp));
		//状态转移方程:是否选择第j个菜品
		for (int i = 1; i <= C; i++) {
			for (int j = 1; j <= N; j++) {
				if (i < p[j]) {//第j个菜品价格大于余额，跳过不选
					dp[i][j] = dp[i][j - 1];
				}
				else {
					//可选时，比较不选和选哪个的评分和最大
					//注意每个菜品仅能选一次
					dp[i][j] = max(dp[i][j - 1], dp[i - p[j]][j - 1] + v[j]);
				}
			}
		}
		printf("%d\n", dp[C][N]);
	}
	return 0;
}