记录139#includebits/stdc.h using namespace std; const int N30; int v; // 定义全局变量v表示需要的维他命种类数 int need[N]; // 记录每种维他命每天需要的最小量 int g; // 定义全局变量g表示饲料的种数 int feed[N][N]; // 二维数组feed[i][j]表示第i种饲料含有的第j种维他命量 int path[N]; // 记录当前搜索路径中选择的饲料编号 bool foundfalse; // 标记是否已经找到了最优解 // 检查当前路径中选择的饲料是否满足所有维他命的需求 bool check(int cnt){ int sum[N]{}; // 临时数组记录当前组合下每种维他命的总量 for(int i1;icnt;i){ // 遍历当前选中的每一种饲料 int idpath[i]; // 获取该饲料的编号 for(int j1;jv;j){ // 累加该饲料提供的各种维他命 sum[j]feed[id][j]; } } for(int i1;iv;i){ // 检查每种维他命是否达标 if(sum[i]need[i]){ // 如果有任何一种维他命不足 return false; // 返回不合法 } } return true; // 所有维他命均满足需求 } // 深度优先搜索DFS函数cur表示当前正在选第几个cnt表示总共需要选几个 void dfs(int cur,int cnt){ if(found) return;// 如果已经找到了最优解因为我们是按数量从小到大搜的找到即最优 // 直接剪枝返回 if(curcnt){ // 如果已经选够了cnt种饲料越界收网 if(check(cnt)){ // 检查当前方案是否满足维他命需求 coutcnt; // 输出最少的饲料种数 for(int i1;icnt;i) cout path[i]; // 按顺序输出选择的饲料编号 foundtrue; // 标记已找到后续搜索全部剪枝 } return; // 结束当前递归分支 } // 从上一个选择的饲料编号1开始枚举保证选择的饲料编号是递增的字典序最小 // 剪枝剩下的饲料数量必须足够凑齐cnt种 for(int ipath[cur-1]1;ig-(cnt-cur1)1;i){ path[cur]i; // 选择第i种饲料 dfs(cur1,cnt); // 继续选择下一种 } } int main(){ // 主函数入口 ios::sync_with_stdio(false); // 关闭标准流同步提升输入输出效率 cin.tie(0); // 解除cin与cout的绑定加快读取速度 cinv; // 读入维他命种类数v for(int i1;iv;i) cinneed[i]; // 读入每种维他命的需求量 cing; // 读入饲料种数g for(int i1;ig;i){ // 读入每种饲料的维他命含量 for(int j1;jv;j) cinfeed[i][j]; } // 从小到大枚举需要选择的饲料种数1种2种3种... for(int i1;ig;i){ path[0]0; // 初始化路径起点为0保证第一个饲料从1开始选 dfs(1,i); // 尝试选i种饲料 if(found) break;// 如果找到了直接跳出循环 } return 0; // 程序正常结束 }题目传送门https://www.luogu.com.cn/problem/P1460前言我是一名专注信奥赛CSP-J/S、NOIP的教练。如果你觉得这篇题解对你有帮助欢迎点击关注我的CSDN账号我会持续更新高质量算法解析。我深知算法思维的构建远比单纯通过题目更重要本系列题解不局限于AC代码的堆砌而是致力于拆解题目背后的逻辑链条与核心知识点备赛路上若遇瓶颈欢迎随时评论或私信我将甄选典型疑难问题通过视频讲解或撰写专项文章的形式为你提供深度答疑。核心解题思路这道题是一道经典的迭代加深搜索Iterative Deepening Search, IDS问题。问题转化与策略选择题目要求我们选出最少的饲料种数并且在种数相同的情况下输出字典序最小的饲料编号组合。由于饲料种数 g≤15g≤15 数据规模较小我们可以直接枚举。但如果我们直接暴力搜索所有子集很难保证找到的第一个解就是“种数最少”的。因此我们采用迭代加深的策略从选 1 种饲料开始尝试如果找不到可行解再尝试选 2 种依此类推。这样我们找到的第一个可行解必然就是饲料种数最少的最优解。保证字典序最小在 DFS 搜索过程中我们强制让选择的饲料编号严格递增即下一个选择的饲料编号必须大于上一个。这样当我们从小到大枚举饲料时自然保证了最终输出的组合是字典序最小的。全局剪枝因为我们是按照饲料种数从少到多进行搜索的一旦在某一层比如选 k 种找到了一个可行解那么它一定是最优的。此时我们可以设置一个全局标志位found直接终止所有后续的搜索极大提升效率。代码分块详细解释1. 头文件、常量与全局变量定义#includebits/stdc.h using namespace std; const int N30; int v; // 定义全局变量 v表示需要的维他命种类数 int need[N]; // 记录每种维他命每天需要的最小量 int g; // 定义全局变量 g表示饲料的种数 int feed[N][N]; // 二维数组feed[i][j] 表示第 i 种饲料含有的第 j 种维他命量 int path[N]; // 记录当前搜索路径中选择的饲料编号 bool foundfalse; // 标记是否已经找到了最优解详细分析path数组是本题记录答案的关键它用来存储当前 DFS 路径上选中的饲料编号。found是一个全局剪枝变量配合迭代加深的策略一旦找到答案就彻底停止搜索。2. 合法性检查函数check// 检查当前路径中选择的饲料是否满足所有维他命的需求 bool check(int cnt){ int sum[N]{}; // 临时数组记录当前组合下每种维他命的总量 for(int i1;icnt;i){ // 遍历当前选中的每一种饲料 int idpath[i]; // 获取该饲料的编号 for(int j1;jv;j){ // 累加该饲料提供的各种维他命 sum[j]feed[id][j]; } } for(int i1;iv;i){ // 检查每种维他命是否达标 if(sum[i]need[i]){ // 如果有任何一种维他命不足 return false; // 返回不合法 } } return true; // 所有维他命均满足需求 }详细分析当 DFS 选够了指定数量cnt的饲料后调用此函数进行验证。它遍历path数组中选中的饲料将它们对应的维他命含量累加到sum数组中最后逐一与need数组中的最低需求量进行比较。只要有一种维他命不达标当前组合即为无效。3. 核心逻辑DFS 与字典序保证// 深度优先搜索DFS函数cur 表示当前正在选第几个cnt 表示总共需要选几个 void dfs(int cur, int cnt){ if(found) return; // 如果已经找到了最优解直接剪枝返回 if(cur cnt){ // 如果已经选够了 cnt 种饲料越界收网 if(check(cnt)){ // 检查当前方案是否满足维他命需求 cout cnt; // 输出最少的饲料种数 for(int i1;icnt;i) cout path[i]; // 按顺序输出选择的饲料编号 found true; // 标记已找到后续搜索全部剪枝 } return; // 结束当前递归分支 } // 从上一个选择的饲料编号1开始枚举保证选择的饲料编号是递增的字典序最小 // 剪枝剩下的饲料数量必须足够凑齐 cnt 种 for(int i path[cur-1] 1; i g - (cnt - cur 1) 1; i){ path[cur] i; // 选择第 i 种饲料 dfs(cur1, cnt); // 继续选择下一种 } }详细分析这是代码的灵魂。字典序保证for循环的起始条件i path[cur-1] 1是核心。它强制要求下一个选择的饲料编号必须大于上一个从而保证了选出的组合是严格递增的自然满足字典序最小的要求。可行性剪枝循环的终止条件i g - (cnt - cur 1) 1是一个经典的组合数学剪枝。它的意思是当前还剩cnt - cur 1个位置需要填充如果从当前位置i往后数剩下的饲料总数不够填满这些位置那么继续枚举i及其后面的数就没有意义了直接跳出循环。全局最优剪枝一旦check通过输出答案并将found置为true所有的递归层都会因为开头的if(found) return而迅速退出。4. 主函数迭代加深框架int main(){ ios::sync_with_stdio(false); cin.tie(0); cin v; // 读入维他命种类数 v for(int i1;iv;i) cin need[i]; // 读入每种维他命的需求量 cin g; // 读入饲料种数 g for(int i1;ig;i){ // 读入每种饲料的维他命含量 for(int j1;jv;j) cin feed[i][j]; } // 从小到大枚举需要选择的饲料种数1种2种3种... for(int i1;ig;i){ path[0]0; // 初始化路径起点为 0保证第一个饲料从 1 开始选 dfs(1, i); // 尝试选 i 种饲料 if(found) break; // 如果找到了直接跳出循环 } return 0; }详细分析主函数完美实现了迭代加深的框架。外层for循环从 1 到 gg 依次枚举需要选择的饲料数量。path[0]0的初始化是为了配合 DFS 中的path[cur-1] 1确保第一种饲料可以从编号 1 开始合法选择。一旦found变为真立刻break保证了答案的绝对最优性。核心逻辑总结表代码模块核心变量/操作精炼作用解决的痛点迭代加深框架主函数中的for(int i1;ig;i)从小到大枚举选择的饲料种数保证了找到的第一个解必然是饲料种数最少的最优解字典序保证i path[cur-1] 1强制下一个选择的编号大于上一个避免了重复组合并天然保证了输出结果的字典序最小可行性剪枝i g - (cnt - cur 1) 1限制枚举的上界当剩余饲料不足以凑齐目标数量时提前终止大幅减少无效搜索全局最优剪枝if(found) return找到答案后立即停止所有递归避免了在找到最优解后继续浪费时间去搜索更差或同级的解合法性验证check(cnt)函数累加维他命并比对最低需求在搜索树的叶子节点准确判定当前饲料组合是否有效路径记录path[N]数组记录 DFS 过程中选中的饲料编号将搜索状态与最终答案的输出完美解耦