题解 | #点菜问题#

#include <cstdio>
#include <iostream>
#include <cstring>

using namespace std;

//01背包问题求解实现中最难最绕的地方：二维数组的思想用一维数组表达
//思考：dp[i][j]表示把 前i件 物品 放进容量j的背包里  i是下标（所以背包问题确实就是前面那些问题的推广） 
//这样就和前面的分析思想很类似了  
//其状态转移：
//情况1：i不放进背包 则dp[i][j] = dp[i-1][j] 
//情况2：i放进背包 则dp[i][j] = v[i] + dp[i][j-w[i]] 注意每件物品 既有价值，又有重量 
//取两个情况的最大值
//现在思考：如何把这个二维数组dp变为用一维数组表示？ 
//事实上逻辑是这样的：因为目标是求dp[n][m]，前面的所有行最后都是不需要的
//并且每一步只须用到相邻两行，而不需要“遍历”
//并且这相邻两行的操作“用左上方来更新右下方”的
//所以可以化为用一维表示！
//太清晰了xdm。 
//每波从右往左更新。
//盯着这个一维数组dp：更新了的部分是对应二维数组中第i行的数据   未更新的部分是对应二维数组中第i-1行的数据 
//然后整体规律上是：单次更新过程中：涉及的i-1行的数据在i行的数据的左侧 
//因此选择从右往左更新。 
//更新过程上，逻辑上还是要每行每个元素都更新 因为更新时每个元素都可能被用到 

const int MAXN = 100 + 10; //物品数目上限 
const int MAXM = 1000 + 10; //容量上限 

int dp[MAXM];//只保留了“容量”下标，而“件”的下标随着逻辑动态变化 
int v[MAXN];
int w[MAXN]; 

int main(){
	int m, n;//m是容量，n是物品数目
	while(scanf("%d%d", &m, &n) != EOF){
		memset(dp, 0, sizeof(dp));//“前0件物品”放入各种容量中的结果 
		for(int i=1; i<=n; i++){
			scanf("%d%d", &w[i], &v[i]);
		}
		for(int i=1; i<=n; i++){//虚空的“行” 但其实不虚空，因为w和v用到了i这个下标 
			for(int j=m; j>=w[i]; j--){//逻辑：如果当前选定的容量j连i都放不下的话  
										//那就是直接继承dp[i-1][j]
										//在这个一维表示法中表现出来就是  对dp[j]不作修改。 太帅了
				dp[j] = max(dp[j], dp[j-w[i]] + v[i]);//赋值号左边的dp默认行号i，右边的默认行号i-1 
			}
		}
		printf("%d\n", dp[m]);
	} 
	return 0;
}