不优化
#include<iostream>
#include<vector>
using namespace std;
const int N = 1010;
int v[N], w[N];
int main()
{
int n, V;
cin >> n >> V;
for (int i = 1; i <= n; i++)
cin >> v[i] >> w[i];
vector<vector<int>> dp(n + 1, vector<int>(V + 1));
for (int i = 1; i <= n; i++)
{
for (int j = 0; j <= V; j++)
{
dp[i][j] = dp[i - 1][j];
if (j >= v[i]) dp[i][j] = max(dp[i][j], dp[i][j - v[i]] + w[i]);
}
}
cout << dp[n][V];
return 0;
}
使用滚动数组优化
#include<iostream>
#include<vector>
using namespace std;
const int N = 1010;
int v[N], w[N];
int main()
{
int n, V;
cin >> n >> V;
for (int i = 1; i <= n; i++)
cin >> v[i] >> w[i];
vector<int> dp(V + 1);
for (int i = 1; i <= n; i++)
{
for (int j = v[i]; j <= V; j++)
{
dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
}
}
cout << dp[V];
return 0;
}