1579. [算法课动态规划]背包问题

#include <bits/stdc++.h> using namespace std; using ll = long long; const ll mn = 502, inf = 1e9; ll n, c, w[mn], v[mn], dp[mn]; signed main() { ios::sync_with_stdio(false), cin.tie(0); cin >> n >> c; for (int i = 1; i <= n; ++i) { cin >> w[i]; } for (int i = 1; i <= n; ++i) { cin >> v[i]; } for (int i = 1; i <= c; ++i) { dp[i] = -inf; } for (ll i = 1; i <= n; ++i) { for (ll j = c - w[i]; j >= 0; --j) { dp[j + w[i]] = max(dp[j + w[i]], dp[j] + v[i]); } } ll ans = 0; for (ll i = 0; i <= c; ++i) { ans = max(ans, dp[i]); } cout << ans; return 0; }