题解 | #【模板】完全背包#

#include <bits/stdc++.h>
using namespace std;
/* clang-format on */
const auto io_sync_off = []() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return nullptr;
}
();



int w[1000];
int v[1000];
int dp[1000];
int main() {
    int n, V;
    cin >> n >> V;
    for (int i = 0; i < n; i++) {
        cin >> v[i] >> w[i];
    }
    memset(dp, 0, sizeof dp);
    for (int i = 0; i < n; i++) {
        for (int j = v[i]; j <= V; j++) { //可以重复选（重复叠加同一个物品），所以用顺序，若只有1件物品，倒序推就不会重复计算
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
        }
    }
    int mx = dp[V];
    memset(dp, -0x3f, sizeof dp);
    dp[0] = 0;
    for (int i = 0; i < n; i++) {
        for (int j = v[i]; j <= V; j++) { 
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
        }
    }
    printf("%d\n%d\n", max(mx, 0), max(dp[V], 0));

}