完全背包问题，记忆化搜索，不能暴力了呜呜呜呜呜

解题思路:

注意事项:

参考代码:

#include"bits/stdc++.h"
using namespace std;
// 定义全局变量，m表示背包容量，n表示物品数量，h初始化为-1
int m, n, h = -1;
// 定义两个数组，wi存储每个物品的重量，vi存储每个物品的价值
int wi[50], vi[50];
// 定义二维数组mem用于记忆化搜索，避免重复计算
int mem[210][210];
int dfs(int x, int y) {
    // 如果当前状态已经计算过，直接返回保存的结果
    if (mem[x][y]) {
        return mem[x][y];
    }
    int sum; // 定义sum变量用于存储当前状态的最大价值
    // 如果所有物品都已经考虑完，返回0
    if (x > n) {
        return 0;
    }
    // 如果当前物品重量大于剩余容量，只能考虑下一个物品
    if (y < wi[x]) {
        sum = dfs(x + 1, y);
    } else {
        // 否则，取不选当前物品和选当前物品两种情况的最大值
        sum = max(dfs(x + 1, y), dfs(x, y - wi[x]) + vi[x]);
    }
    // 将当前状态的最大价值保存到mem数组中
    mem[x][y] = sum;
    // 返回当前状态的最大价值
    return sum;
}
int main() {
    // 输入背包容量和物品数量
    cin >> m >> n;
    // 输入每个物品的重量和价值
    for (int i = 1; i <= n; i++) {
        cin >> wi[i] >> vi[i];
    }
    // 输出最大价值结果
    cout << "max=" << dfs(1, m) << endl;
    return 0;
}