题解：P11377 [GESP202412 七级] 武器购买

chenxiangjun · 2024-12-10 21:59:37 · 题解

题目意思概括：

t组数据，对于每组数据 n 个物品无法在 Q 价钱让 总强度 > P

思路：背包

1.判断类型

根据样例显然是01背包

2.推导转移方程

(1)让 dp_i 为 花费为 i 时 最大总强度为 dp_i

背包代码如下

for(int i=1;i<=n;i++)//背包 
{
        for(int j=Q;j>=c[i];j--)
        {
            dp[j]=max(dp[j],dp[j-c[i]]+p[i]);
        }
    }

完整代码如下

温馨提示多测要清空

#include<bits/stdc++.h>//具体解析见上 
using namespace std;
int t,n,P,Q;
int p[50500],c[50500],dp[50500];//开大点数组好习惯 
int main()
{
    ios::sync_with_stdio(false);//同步 输入输出减少一些时间 
    cin.tie(0);
    cout.tie(0);
    cin>>t;
    while(t--)
    {
        cin>>n>>P>>Q;
        for(int i=1;i<=n;i++)
        {
            cin>>p[i]>>c[i];
        }
        memset(dp,0,sizeof(dp));//多测清空
        for(int i=1;i<=n;i++)//背包 
        {
            for(int j=Q;j>=c[i];j--)
            {
                dp[j]=max(dp[j],dp[j-c[i]]+p[i]);
            }
        }
        if(dp[Q]<P) cout<<"-1\n";//输出
        else 
        {
            for(int i=1;i<=Q;i++)//正序寻找ans 
            {
                if(dp[i]>=P)
                {
                    cout<<i<<'\n';
                    break;
                }
            }
        }
    }

    return 0;
}

本蒟蒻第一篇题解求过