P3985 不开心的金明
#include #include using namespace std; int w[101],v[101]; map > dp; int n,W; long long dfs(int i,int zl) { if (dp[i][zl]>0) return dp[i][zl]; if (i==n+1) return 0; else { if(zl>=w[i]) { return dp[i][zl]=max(dfs(i+1,zl-w[i])+v[i],dfs(i+1,zl)); } else return dp[i][zl]=dfs(i+1,zl); } } int main() { cin>>n>>W; for (int i=1;i<=n;i++) { cin>>w[i]>>v[i]; } cout<