hdu2159-FATE

题目入口
完全背包：dp[i]:耐力消耗为i时的最大经验，用num[i]记录消灭数量

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e3+10;
int v[MAXN],w[MAXN];
int dp[MAXN];
int num[MAXN];
int main(){
    int n,m,k,s,V;
    while(cin>>V>>m>>n>>s){
        for(int i=1;i<=n;i++){
            cin>>v[i]>>w[i];
        }
        memset(dp,0,sizeof(dp));
        memset(num,0,sizeof(num));
        for(int i=1;i<=n;i++){
            for(int j=w[i];j<=m;j++){
                if(dp[j]<dp[j-w[i]]+v[i]){
                    dp[j]=dp[j-w[i]]+v[i];
                    num[j]=num[j-w[i]]+1;
                }
            }
        }
        bool ok=false;
        for(int i=1;i<=m;i++){
            if(dp[i]>=V&&num[i]<=s){
                cout<<m-i<<endl;
                ok=true;break;
            }
        }
        if(!ok)cout<<"-1"<<endl;
    }



    return 0;
}

hdu2159-FATE

原文：https://www.cnblogs.com/qq103013999/p/12833719.html