方法二：状态压缩

#include <bits/stdc++.h>
using namespace std;
int main() {
    int M, N;  // M 是背包容量，N 是物品数量
    cin >> M >> N;

    // 动态数组存储每个物品的重量和价值
    vector<int> W(N), C(N);
    for (int i = 0; i < N; ++i) {
        cin >> W[i] >> C[i];  // 输入每个物品的重量和价值
    }
    // 动态数组 dp，大小为 M + 1，初始值为 0
    vector<int> dp(M + 1, 0);

    // 完全背包问题的核心遍历
    for (int i = 0; i < N; ++i) {  // 遍历每个物品
        for (int j = W[i]; j <= M; ++j) {  // 遍历背包容量，从小到大遍历
            dp[j] = max(dp[j], dp[j - W[i]] + C[i]);  // 状态转移
        }
    }

    // 输出结果，即背包容量为 M 时的最大价值
    cout <<"max="<<dp[M] << endl;

    return 0;
}