//不优化
include[HTML_REMOVED]
include[HTML_REMOVED]
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[HTML_REMOVED]> dp(n + 1, vector[HTML_REMOVED](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 - 1][j - v[i]] + w[i]);
}
}
cout << dp[n][V];
return 0;
}
使用滚动数组优化
include[HTML_REMOVED]
include[HTML_REMOVED]
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[HTML_REMOVED] dp(V + 1);
for (int i = 1; i <= n; i++)
{
for (int j = V; j>=v[i]; j--)
{
dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
}
}
cout << dp[V];
return 0;
}