题目描述

01背包

算法1

(记忆化搜索)

时间复杂度

太菜了不会算

参考文献

https://www.luogu.com.cn/blog/interestingLSY/memdfs-and-dp

C++ 代码

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

using namespace std;

const int N = 1010,inf = 0x3f3f3f3f;
int v[N],w[N],mem[N][N];        // mem 记录之前搜过的状态
int n,m;

int dfs(int u,int left)         // u表示枚举的第几个物品
{
    if(mem[u][left] != -1) return mem[u][left]; // 如果当前状态被搜过，直接返回
    if(u == n + 1) return mem[u][left] = 0;
    int dfs1,dfs2;
    dfs1 = dfs2 = -inf;
    dfs1 = dfs(u + 1,left);                     // 不选第i个物品
    if(left - v[u] >= 0)                        // 在能够放第i个物品的情况下，选第i个物品
         dfs2 = dfs(u + 1,left - v[u]) + w[u];
    return mem[u][left] = max(dfs1,dfs2);       // 返回两者之间的较大值
}

int main()
{
    cin >> n >> m;
    memset(mem,-1,sizeof mem);
    for(int i = 1; i <= n; i ++)
        cin >> v[i] >> w[i] ;

    cout << dfs(1,m) << endl;
}