欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！
专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。
适合人群：
- 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
- 希望系统学习C++/Python编程的初学者
- 想要提升算法与编程能力的编程爱好者
附上汇总帖：GESP认证C++编程真题解析 | 汇总
【题目来源】
洛谷：P11377 [GESP202412 七级] 武器购买 - 洛谷
【题目描述】
商店里有n nn个武器，第i ii个武器的强度为p i p_ipi，花费为c i c_ici。
小杨想要购买一些武器，满足这些武器的总强度不小于P PP，总花费不超过Q QQ，小杨想知道是否存在满足条件的购买方案，如果有，最少花费又是多少。
【输入】
第一行包含一个正整数 ，代表测试数据组数。
对于每组测试数据，第一行包含三个正整数n , P , Q n,P,Qn,P,Q，含义如题面所示。
之后n nn行，每行包含两个正整数p i , c i p_i,c_ipi,ci，代表武器的强度和花费。
【输出】
对于每组测试数据，如果存在满足条件的购买方案，输出最少花费，否则输出− 1 -1−1。
【输入样例】
3 3 2 3 1 2 1 2 2 3 3 3 4 1 2 1 2 2 3 3 1000 1000 1 2 1 2 2 3【输出样例】
3 -1 -1【算法标签】
《洛谷 P11377 武器购买》 #动态规划DP# #背包DP# #GESP# #2024#
【代码详解】
#include<bits/stdc++.h>usingnamespacestd;constintN=105;// 最大物品数量constintMAX_COST=5000005;// 最大成本，需要根据题目要求调整intt;// 测试用例数量intn,P,Q;// n: 物品数量, P: 需要的最小收益, Q: 最大可用成本intp[N],c[N];// p[i]: 第i件物品的收益, c[i]: 第i件物品的成本intdp[MAX_COST];// dp[j]: 花费成本不超过j时能获得的最大收益intmain(){cin>>t;// 读取测试用例数量// 处理每个测试用例while(t--){// 输入当前测试用例的数据cin>>n>>P>>Q;// 初始化dp数组为0memset(dp,0,sizeof(dp));// 输入每件物品的收益和成本for(inti=1;i<=n;i++){cin>>p[i]>>c[i];}// 01背包动态规划// 外层循环：遍历每件物品for(inti=1;i<=n;i++){// 内层循环：反向遍历成本（从大到小）// 确保每件物品最多被选一次for(intj=Q;j>=c[i];j--){// 状态转移方程：// 1. 不选第i件物品：dp[j]保持不变// 2. 选第i件物品：dp[j-c[i]] + p[i]dp[j]=max(dp[j],dp[j-c[i]]+p[i]);}}// 寻找最小成本使得收益至少达到Pboolflag=0;// 标记是否找到符合条件的成本for(inti=0;i<=Q;i++){if(dp[i]>=P)// 如果花费成本i能获得至少P的收益{cout<<i<<endl;// 输出最小成本flag=1;// 标记已找到break;// 找到第一个就退出，因为i是从小到大遍历的}}// 如果没有找到符合条件的成本if(!flag){cout<<-1<<endl;// 输出-1表示无解}}return0;}【运行结果】
3 3 2 3 1 2 1 2 2 3 3 3 3 4 1 2 1 2 2 3 -1 3 1000 1000 1 2 1 2 2 3 -1
