#include <iostream> #include<cstdio> #include<algorithm> using namespace std; int w[31], c[31]; int dp[31][201]; int main() { int m, n; cin >> m >> n; //背包容量m和物品数量n for (int i = 1; i <= n; i++) cin >> w[i] >> c[i]; //每个物品的重量和价值 for (int i = 1; i <= n; i++) { //dp[i][j]表示前i件物品，总重量不超过j的最优价值 for (int j = 1; j <= m; j++) { if (j >= w[i]) dp[i][j] = max(dp[i - 1][j], dp[i][j - w[i]] + c[i]); else dp[i][j] = dp[i - 1][j]; } } cout << "max=" << dp[n][m]; // dp[n][m]为最优解 return 0; }