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

本文分享的必刷题目是从蓝桥云课、洛谷、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背包【代码详解】#includebits/stdc.husingnamespacestd;intn,x,y;intf[305][305],a[305],b[305];intmain(){cinnxy;// 输入物品数量和目标值for(inti1;in;i){cina[i]b[i];// 输入每个物品的属性}// 初始化DP数组为无穷大memset(f,0x3f,sizeoff);f[0][0]0;// 不需要任何物品就可以达到(0,0)// 动态规划for(inti1;in;i){// 考虑前i个物品for(intjx;j0;j--){// 反向遍历实现0-1背包for(intky;k0;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;elsecoutf[x][y];return0;}【运行结果】3 5 6 2 1 3 4 2 3 2