1. 问题分析

完全背包dp问题

2. 过程

3. 代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1010;
int n, V, v[N], w[N];
int dp[N];

int main()
{
    cin >> n >> V;
    for(int i = 1;i <= n;i++) cin >> v[i] >> w[i];

    // 第一问
    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] << endl;

    // 第二问
    memset(dp, 0, sizeof(dp));
    for(int i = 1;i <= V;i++) dp[i] = -1;
    
    for(int i = 1;i <= n;i++)
        for(int j = v[i];j <= V;j++)
            if(dp[j-v[i]] != -1)
                dp[j] = max(dp[j], dp[j-v[i]]+w[i]);
    cout << (dp[V] == -1 ? 0 : dp[V]) << endl;

    return 0;
}