题目描述
样例
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 127;
int dp[N][N],v[N],w[N];
int dfs(int n,int m)
{
if(dp[n][m]) return dp[n][m];
if(n == 0 || m <= 0) return 0;
if(v[n]>m) dp[n][m] = dfs(n-1,m);
else dp[n][m] = max(dfs(n-1,m),dfs(n-1,m-v[n]) + w[n]);
return dp[n][m];
}
int main()
{
int n,m;cin >> n >> m;
for(int i = 1 ; i <= n ; i++) cin >> v[i] >> w[i];
cout << dfs(n,m) << endl;//前n件物品,在容量为m的前提下,得到的最大值.
return 0;
}
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 127;
int f[N],v[N],w[N];
int main()
{
int n,m;cin >> n >> m;
for(int i = 1 ; i <= n ; i++) cin >> v[i] >> w[i];
for(int i = 1 ; i <= n ; i++) {//前几件物品
for(int j = m ; j >= v[i] ; j--){
f[j] = max(f[j],f[j-v[i]] + w[i]);
}
}
cout << f[m] << endl;
return 0;
}
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 127;
int f[N][N],v[N],w[N];
int main()
{
int n,m;cin >> n >> m;
for(int i = 1 ; i <= n ; i++) cin >> v[i] >> w[i];
for(int i = 1 ; i <= n ; i++) {//前几件物品
for(int j = 1 ; j <= m ; j++){
f[i][j] = f[i-1][j];
if(j>=v[i]) f[i][j] = max(f[i][j],f[i-1][j-v[i]] + w[i]);
}
}
cout << f[n][m] << endl;
return 0;
}