回溯+记忆搜索 ``` int maxValue(vector<int>&w,vector<int>&v,int capacity){ int n = w.size(); //数组存储已经得到过的dfs{i,c) vector<vector<int>> cache(n,vector<int>(capacity+1,-1)); function<int(int,int)> dfs = [&](int i,int c){ if(i < 0||c < 0) return 0; int& res = cache[i][c]; if(res!=-1) return res; if(c<w[i]){ res = dfs(i-1,c); return res; } res = max(dfs(i,c-w[i])+v[i],dfs(i-1,c)); return res; }; return dfs(n-1,capacity); } ```