P1510 精卫填海

发布时间 2023-08-22 16:36:34作者: 失控D大白兔

东海未填平的区域还需要至少体积为 v 的木石才可以填平,而西山上的木石还剩下 n 块,每块的体积和把它衔到东海需要的体力分别为 k 和 m。
精卫已经填海填了这么长时间了,她也很累了,她还剩下的体力为 c。
如果精卫能把东海填平,则输出她把东海填平后剩下的最大的体力,否则输出 Impossible

1. 动态规划

每个木石是一个物品,体积是物品的价值,消耗体力是物品的质量,总体力c是总容量,
计算不同容量的最大价值,然后从小到大遍历,输出最小满足条件的容量时候的剩余容量

void maxval(int V,vector<int>&c,vector<int>&w,int v){
    int n = c.size();
    vector<int> dp(V+1);
    for(int i=0;i<n;i++)
        for(int j=V;j>=c[i];j--)
            dp[j] = max(dp[j],dp[j-c[i]]+w[i]);

    for(int j=0;j<=V;j++)
        if(dp[j]>=v){
            cout<<V-j;
            return;
        }
    cout<<"Impossible";
    return;
}