问题分析

背包dp问题

过程

代码

#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;j >= v[i];j--)
            dp[j] = max(dp[j], w[i]+dp[j-v[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;j >= v[i];j--)
            if(dp[j-v[i]] != -1)
                dp[j] = max(dp[j], w[i]+dp[j-v[i]]);
    cout << (dp[V] == -1 ? 0 : dp[V]) << endl;

    return 0;
}