题解：学而思编程 智能饭盒

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

【题目来源】

学而思编程：智能饭盒

【题目描述】

有n nn个食物和一个饭盒。第i ii个食物含有a i a_iai​克脂肪和b i b_ibi​克蛋白质。

小猴要选择一些食物装进饭盒里，这是个智能饭盒，可以测定食物的脂肪和蛋白质含量，小猴想要选出的食物合计至少含有x xx克脂肪和y yy克蛋白质。他最少需要选择多少个食物装进饭盒？

【输入】

第1 11行，1 11个正整数n nn

第2 22行，2 22个正整数x , y x,yx,y

接下来n行，每行两个正整数a i , b i a_i,b_iai​,bi​

【输出】

1 11个整数，需要选择的最少食物数；如果无法得到要求的脂肪和蛋白质含量，输出− 1 −1−1。

【输入样例】

3 5 6 2 1 3 4 2 3

【输出样例】

2

【解题思路】

【算法标签】

#01背包

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;intn,x,y;intf[305][305],a[305],b[305];intmain(){cin>>n>>x>>y;// 输入物品数量和目标值for(inti=1;i<=n;i++){cin>>a[i]>>b[i];// 输入每个物品的属性}// 初始化DP数组为无穷大memset(f,0x3f,sizeoff);f[0][0]=0;// 不需要任何物品就可以达到(0,0)// 动态规划for(inti=1;i<=n;i++){// 考虑前i个物品for(intj=x;j>=0;j--){// 反向遍历，实现0-1背包for(intk=y;k>=0;k--){// 状态转移：选或不选第i个物品f[j][k]=min(f[j][k],f[max(j-a[i],0)][max(k-b[i],0)]+1);}}}// 输出结果if(f[x][y]>=0x3f3f3f3f)// 如果不可达cout<<-1;elsecout<<f[x][y];return0;}

【运行结果】

3 5 6 2 1 3 4 2 3 2