题解 | 【模板】完全背包

#include <bits/stdc++.h>

using namespace std;

#define N (int)(1e3+5)

int dp[N];
int dp2[N];
int value[N],volume[N];

int my_max(int a,int b){
    return (a>b)?a:b;
}

int main(){
    int n,V;
    scanf("%d %d",&n,&V);
    for(int i=0;i<n;i++){
        scanf("%d %d",&volume[i],&value[i]);
    }
    for(int i=1;i<=V;i++){
        dp2[i]=INT_MIN;
    }

    for(int i=0;i<n;i++)//遍历每种物品
    {
        //正序可以多次使用物品,累加物品
        for(int j=volume[i];j<=V;j++){
            dp[j]=my_max(dp[j],dp[j-volume[i]]+value[i]);
            dp2[j]=my_max(dp2[j],dp2[j-volume[i]]+value[i]);
        }
    }
    printf("%d\n",dp[V]);
    if(dp2[V]>0) printf("%d\n",dp2[V]);
    else printf("%d\n",0);
    return 0;
}