本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P1460 [USACO2.1] 健康的荷斯坦奶牛 Healthy Holsteins - 洛谷【题目描述】农民 John 以拥有世界上最健康的奶牛为傲。他知道每种饲料中所包含的牛所需的最低的维他命量是多少。请你帮助农夫喂养他的牛以保持它们的健康使喂给牛的饲料的种数最少。给出牛所需的最低的维他命量输出喂给牛需要哪些种类的饲料且所需的饲料剂量最少。维他命量以整数表示每种饲料最多只能对牛使用一次数据保证存在解。【输入】第一行一个整数v表示需要的维他命的种类数。第二行v个整数表示牛每天需要的每种维他命的最小量。第三行一个整数g表示可用来喂牛的饲料的种数。下面g行第n行表示编号为n饲料包含的各种维他命的量的多少。【输出】输出文件只有一行包括牛必需的最小的饲料种数p后面有p个数表示所选择的饲料编号按从小到大排列。如果有多个解输出饲料序号最小的即字典序最小。【输入样例】4 100 200 300 400 3 50 50 50 50 200 300 200 300 900 150 389 399【输出样例】2 1 3【核心思想】问题分析给定v vv种维他命的最小需求量以及g gg种饲料各自含有的维他命量。要求选择最少数量的饲料使得每种维他命的总量均满足最小需求。若有多解输出饲料编号字典序最小的方案。这是一个子集枚举 可行性验证问题。算法选择DFS 枚举子集对每个饲料编号p o s pospos决策选或不选递归搜索所有可能的子集剪枝优化当已选数量c n t ≥ m i n S e l C n t cnt \ge minSelCntcnt≥minSelCnt时提前返回当前已不可能更优可行性验证对选定的饲料子集累加每种维他命的总量判断是否全部满足需求关键步骤读入数据v vv维他命种类数、v [ 1.. v ] v[1..v]v[1..v]最小需求量、g gg饲料种数、f [ i ] [ j ] f[i][j]f[i][j]饲料i ii中维他命j jj的含量DFS 函数dfs(pos, cnt)pos当前考虑的饲料编号cnt已选择的饲料数量终止条件若p o s g pos gposg调用check(cnt)验证当前选择若满足需求且c n t m i n S e l C n t cnt minSelCntcntminSelCnt更新最优解选择当前饲料sel[cnt1] pos递归dfs(pos1, cnt1)不选当前饲料递归dfs(pos1, cnt)验证函数check(selCnt)对每种维他命i ii累加所选饲料中该维他命的含量sum若存在sum v[i]返回false全部满足返回true输出最小选择数及对应的饲料编号时间/空间复杂度时间复杂度O ( 2 g ⋅ v ⋅ g ) O(2^g \cdot v \cdot g)O(2g⋅v⋅g)枚举2 g 2^g2g个子集每个验证O ( v ⋅ g ) O(v \cdot g)O(v⋅g)空间复杂度O ( g ) O(g)O(g)递归深度和选择数组DFS 子集枚举的核心思想二进制决策模型每个饲料只有选或不选两种状态DFS 按编号顺序枚举形成一棵决策树最优性剪枝维护当前最优解m i n S e l C n t minSelCntminSelCnt当c n t ≥ m i n S e l C n t cnt \ge minSelCntcnt≥minSelCnt时无需继续搜索该分支字典序自然保证按编号1 ∼ g 1 \sim g1∼g顺序决策先选后递归首次找到的最小数量解即为字典序最小可行性优先于最优性先找到任意可行解获得m i n S e l C n t minSelCntminSelCnt初值后续搜索以此剪枝适用于子集选择、组合优化、最小覆盖类问题【解题思路】【算法标签】#普及- #DFS-一维【代码详解】#includebits/stdc.husingnamespacestd;intvType,fType,p;intv[30],f[20][30],sel[20],ans[20];intminSelCnt20;boolcheck(intselCnt)// 定义维他命检查函数{for(inti1;ivType;i){// 依次遍历所有维他命种类intsum0;// 定义每种维他命的总数每次循环初始为0for(intj1;jselCnt;j){// 依次遍历选择的那些饲料sumf[sel[j]][i];// sum加上选择的饲料编号的维他命值}if(sumv[i]){// 如果总和returnfalse;}}returntrue;}voiddfs(intpos,intcnt)// 定义dfs函数pos为饲料编号cnt为饲料选择的数量{if(posfType){// dfs退出条件直到选到最后一种饲料编号if(check(cnt)cntminSelCnt){// 如果此时选择的饲料的每种维他命之和大于最小维他命需要且选择数量小于最小选择数量minSelCntcnt;// 更新最小选择数量for(inti1;icnt;i){// 更新结果数组即更新为选择的饲料种类ans[i]sel[i];}}return;// 一定要写}sel[cnt1]pos;// 选择编号为pos的饲料dfs(pos1,cnt1);// 继续选择pos1编号的饲料cnt自增1sel[cnt1]0;// 不选编号为pos的饲料不选就用0占位这句可以忽略因为下一句dfs中cnt不变下次执行后会被修改dfs(pos1,cnt);// 继续dfs搜索pos1编号的饲料但cnt不增加}intmain(){cinvType;// 输入需要的维他命种类数for(inti1;ivType;i){// 遍历维他命种类数cinv[i];// 输入每种维他命的最小量}cinfType;// 输入饲料种数for(inti1;ifType;i){// for循环遍历饲料种数for(intj1;jvType;j){// for循环遍历维他命种类数cinf[i][j];// 输入这种饲料各种维他命的值}}dfs(1,0);// 使用dfs搜索起始饲料编号为10种选择coutminSelCnt ;for(inti1;iminSelCnt;i){coutans[i] ;}return0;}【运行结果】4 100 200 300 400 3 50 50 50 50 200 300 200 300 900 150 389 399 2 1 3