[01背包]洛谷P1510 精卫填海

题目传送门

解题思路

转化为一般的01背包进行求解,最后枚举体力,当目前填的体积>=应该填的体积时,输出最大的体力值。

代码分享

#include <iostream>
#include <cstdio>
#include <cstdlib>

using namespace std;
const int maxn=1001000;
int V,N,C;
int dp[maxn],d[maxn],v[maxn];
//d 价值 v体积
int main() {
    scanf("%d%d%d",&V,&N,&C);
    for(int i=1;i<=N;i++) {
        scanf("%d%d",&v[i],&d[i]);
    } 
    for(int i=1;i<=N;i++) {
        for(int j=C;j>=d[i];j--) {
            dp[j]=max(dp[j],dp[j-d[i]]+v[i]);
        } 
    } 
    for(int i=1;i<=C;i++) {
        if(dp[i]>=V) {
            printf("%d\n",C-i);
            return 0;
        }
    }
    printf("Impossible");
    return 0;
}
点赞

发表评论