算法1：记忆化搜索

C++ 代码

时间复杂度$O(n*capacity)$
参考思路：灵茶山艾府

#include<iostream>
#include<vector>
using namespace std;
const int MX=1005;
//capacity: 背包容量
//w[i]：第 i 个物品的体积
//v[i]：第 i 个物品的价值
int w[MX],v[MX];
int main(){
    int n,capacity;
    cin>>n>>capacity;
    //因为是两个参数，第几个和背包容量，使用二维数组记忆化
    vector<vector<int>> cache(n + 1, vector<int>(capacity + 1, -1));
    for(int i=1;i<=n;i++){
        cin>>w[i]>>v[i];
    }
    auto dfs=[&](auto&&dfs,int i,int c)->int{
        if(i<=0){
            return 0;
        }
        if(cache[i][c] != -1){
            return cache[i][c];
        }
        if(c<w[i]){
            return dfs(dfs,i-1,c);
        }

        return cache[i][c]=max(dfs(dfs,i-1,c),dfs(dfs,i-1,c-w[i])+v[i]);
    };
    cout<<dfs(dfs,n,capacity)<<endl;
}

算法2：递推

时间复杂度

参考文献

C++ 代码

blablabla