题解 | #点菜问题#

#include using namespace std;

const int MAXN = 1000 + 10;

int weight[MAXN]; int value[MAXN]; int dp[MAXN][MAXN];

int main() { int n, m; //输入物品的数量和背包的容量 while (cin >> m >> n) { for (int i = 1; i <= n; i++) { //默认从下标为1的位置开始 cin >> weight[i] >> value[i]; //输入重量和价值 } //对dp数组进行初始化 for (int i = 0; i <= n; i++) { dp[i][0] = 0; //背包容量为零的情况下 } for (int j = 0; j <= m; j++) { dp[0][j] = 0; //不选物品的情况下 } for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (j < weight[i]) { dp[i][j] = dp[i - 1][j]; } else { dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); }

		}
	}
	cout << dp[n][m] << endl;
}

system("pause");
return 0;

}