之前一直分不清记忆化搜索和暴力减枝的区别，现在通过最简单的01背包来mark一下这两者的不同，以及记忆化搜索的特点。

纯暴力

很显然,可以想到$dfs(u,sum,value)$ 表示从第u个物品开始取，总体积是sum，总贡献是value，暴力深搜所有解法
1.先dfs不选第u种物品的情况
2.再考虑选第u种物品的情况

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N];
int ans;

int dfs(int u, int sum, int value)
{
    if (u == n) ans = max(ans, value);
    else
    {
        dfs(u + 1, sum, value);

        if (sum + v[u] <= m)
            dfs(u + 1, sum + v[u], value + w[u]);
    }
}

int main()
{
    freopen("input.txt", "r", stdin);
    //freopen("DFS.txt", "w", stdout);

    cin >> n >> m;

    for (int i = 0; i < n; i ++ ) cin >> v[i] >> w[i];

    dfs(0, 0, 0);

    cout << ans << endl;
    return 0;
}

另一种暴力写法

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N];
int ans;


int dfs(int i,int j)//从第i个物品开始挑选总重量小于j的部分
{
    int res;
    //已经没有剩余物品
    if (i == n) res = 0;
    //无法挑选第i个物品
    else if (j < v[i]) res = dfs(i+1,j);
    //比较挑和不挑的情况，选取最大的情况
    else res = max(dfs(i+1,j),dfs(i+1,j-v[i]) + w[i]);
    return res;
}
//入口:dfs(0,m);




int main()
{
    freopen("input.txt", "r", stdin);
    //freopen("DFS.txt", "w", stdout);

    cin >> n >> m;

    for (int i = 0; i < n; i ++ ) cin >> v[i] >> w[i];

    cout << dfs(0,m) << endl;
    return 0;
}

记忆化搜索

我们可以得出使用dfs的时间复杂度为O(2^n)。显然这个方法不是一个很好的方法，因为这个时间复杂度太高了。我们仔细研究可以发现，造成时间复杂度这么高的原因是重复计算。既然我们找到复杂度这么高的原因，那我们就可以想办法减少它重复计算的次数。仔细分析容易想到，使用一个二维数组来记录每一次搜索的答案，这样我们就避免了重复计算。

记忆化搜索要点：先初始化一个记忆数组全为-1
若当前暴力经过之前经过的状态则不往下走，直接返回那个状态的值

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N];
int ans;


int f[N][N];
int dfs(int i,int j)
{
    int &x = f[i][j];
    if (x > -1) return x;
    if (i == n) x = 0;
    else if (j < v[i]) x = dfs(i + 1,j);
    else x = max(dfs(i+1,j),dfs(i + 1,j - v[i]) + w[i]);
    return x; 
}




int main()
{
    //freopen("input.txt", "r", stdin);
    //freopen("DFS.txt", "w", stdout);

    cin >> n >> m;

    for (int i = 0; i < n; i ++ ) cin >> v[i] >> w[i];

    //dfs(0, 0, 0);
    memset(f,-1,sizeof(f));
    cout << dfs(0,m) << endl;
    return 0;
}

dp很简单，这就略过了