算法题解析最小成本采购材料贪心最小堆实战在日常开发中我们经常会遇到类似“资源最优分配”的问题今天要解析的这道采购材料题就是典型的贪心算法应用场景结合最小堆优先队列就能高效求解。题目看似简单但能帮我们理清贪心策略的核心逻辑话不多说直接进入正题。一、题目描述清晰易懂版现有若干供应商每个供应商提供的材料有两个关键信息基础单价和库存数量。特别注意的是每个供应商的材料每卖出1单位下1单位的单价就会在基础单价的基础上1比如基础单价9元买第1个9元第2个10元第3个11元以此类推。我们需要采购n个单位的材料如何选择采购顺序才能让总花费最少示例输入# 供应商列表[[基础单价, 库存数量], ...]suppliers[[100,200],[9,2],[10,3],[10,1],[10,3]]# 需采购的总数量n4示例输出39二、题目核心分析这道题的关键矛盾点的是供应商的单价会随采购数量递增而我们要在有限的采购量n个内尽可能选择“当前最便宜”的单位才能实现总花费最小。这里有两个核心观察局部最优 → 全局最优每一步都选择当前最便宜的1单位材料最终的总花费一定是最小的贪心算法的核心思想。需要高效获取“当前最便宜单价”如果每次都遍历所有供应商找最低价效率太低此时用最小堆优先队列就能完美解决——堆顶永远是当前最小的元素获取和更新都很高效。三、算法选择贪心 最小堆结合上面的分析我们确定算法方案用最小堆维护所有可采购的材料单价每次从堆顶取出最便宜的1单位完成采购后若该供应商还有库存就将“涨价后的单价”重新加入堆中重复此过程直到采购够n个单位。算法核心步骤结合示例拆解先梳理示例中的供应商筛选有效供应商忽略单价过高、库存为0的干扰项供应商A基础单价9元库存2性价比最高供应商B基础单价10元库存3供应商C基础单价10元库存1供应商D基础单价10元库存3供应商E基础单价100元库存200单价过高初期不考虑采购目标n4个单位逐步拆解每一步初始化最小堆将所有供应商的基础单价库存加入堆中堆顶为当前最低价9元供应商A。第1次采购取堆顶9元库存2花费9采购数量count1。供应商A库存剩余1下一个单价变为9110元将10元1重新加入堆中。第2次采购堆顶变为10元供应商A花费10累计19采购数量count2。供应商A库存耗尽不再加入堆中。第3次采购堆顶为10元供应商B/C/D均可此处选B花费10累计29采购数量count3。供应商B库存剩余2下一个单价变为10111元将11元2重新加入堆中。第4次采购堆顶仍为10元供应商C花费10累计39采购数量count4达到目标停止采购。最终总花费39元与示例输出一致验证了算法的正确性。四、算法伪代码通用版伪代码清晰梳理逻辑适配任何类似输入场景# 1. 初始化最小堆heap空最小堆for每个(base_price,stock)in供应商列表:ifstock0:# 只加入有库存的供应商heappush(heap,(base_price,stock))# 2. 初始化总花费和采购计数total_cost0# 总花费purchase_count0# 已采购数量# 3. 循环采购直到够n个或无供应商可采购whileheap 不为空 且 purchase_countn:# 取出当前最便宜的材料堆顶元素current_price,current_stockheappop(heap)# 采购1个单位total_costcurrent_price purchase_count1# 若该供应商还有库存涨价后重新加入堆ifcurrent_stock1:heappush(heap,(current_price1,current_stock-1))# 4. 返回总花费returntotal_cost五、复杂度分析为什么这个算法高效算法的效率主要取决于堆操作的时间复杂度我们来拆解一下初始化堆遍历所有供应商共M个供应商时间复杂度O(M log M)每次入堆操作是O(log M)。采购循环共执行n次每次循环包含1次出堆O(log M)和最多1次入堆O(log M)总时间复杂度O(n log M)。整体时间复杂度为O(M log M n log M)其中M是供应商数量n是采购数量。在实际场景中n和M通常不会特别大这个算法的效率完全够用属于最优解决方案。六、Python代码实现可直接运行结合示例输入写出可直接运行的代码方便大家调试和复用importheapqdefmin_purchase_cost(suppliers,n):# 初始化最小堆过滤掉库存为0的供应商heap[]forprice,stockinsuppliers:ifstock0:heapq.heappush(heap,(price,stock))total0count0whileheapandcountn:current_price,current_stockheapq.heappop(heap)# 采购1个totalcurrent_price count1# 库存剩余涨价后入堆ifcurrent_stock1:heapq.heappush(heap,(current_price1,current_stock-1))returntotal# 示例输入suppliers[[100,200],[9,2],[10,3],[10,1],[10,3]]n4# 调用函数输出结果print(min_purchase_cost(suppliers,n))# 输出39七、总结与拓展这道题的核心是“贪心策略”的应用——每一步都追求局部最优最终实现全局最优。而最小堆则是贪心策略的“好帮手”帮我们高效获取当前最优解避免了暴力遍历的低效。拓展思考如果题目新增限制比如每个供应商最多采购k个单位、采购有运输成本等只需在入堆、出堆时增加对应判断核心逻辑依然是“贪心最小堆”可见这种思路的通用性。其实算法并不难关键是找到“局部最优”的切入点再用合适的数据结构比如这里的最小堆提升效率。希望这篇解析能帮大家理清思路下次遇到类似的最优分配问题能快速想到对应的解决方案
算法题解析：最小成本采购材料（贪心+最小堆实战）
发布时间：2026/5/15 23:27:24
算法题解析最小成本采购材料贪心最小堆实战在日常开发中我们经常会遇到类似“资源最优分配”的问题今天要解析的这道采购材料题就是典型的贪心算法应用场景结合最小堆优先队列就能高效求解。题目看似简单但能帮我们理清贪心策略的核心逻辑话不多说直接进入正题。一、题目描述清晰易懂版现有若干供应商每个供应商提供的材料有两个关键信息基础单价和库存数量。特别注意的是每个供应商的材料每卖出1单位下1单位的单价就会在基础单价的基础上1比如基础单价9元买第1个9元第2个10元第3个11元以此类推。我们需要采购n个单位的材料如何选择采购顺序才能让总花费最少示例输入# 供应商列表[[基础单价, 库存数量], ...]suppliers[[100,200],[9,2],[10,3],[10,1],[10,3]]# 需采购的总数量n4示例输出39二、题目核心分析这道题的关键矛盾点的是供应商的单价会随采购数量递增而我们要在有限的采购量n个内尽可能选择“当前最便宜”的单位才能实现总花费最小。这里有两个核心观察局部最优 → 全局最优每一步都选择当前最便宜的1单位材料最终的总花费一定是最小的贪心算法的核心思想。需要高效获取“当前最便宜单价”如果每次都遍历所有供应商找最低价效率太低此时用最小堆优先队列就能完美解决——堆顶永远是当前最小的元素获取和更新都很高效。三、算法选择贪心 最小堆结合上面的分析我们确定算法方案用最小堆维护所有可采购的材料单价每次从堆顶取出最便宜的1单位完成采购后若该供应商还有库存就将“涨价后的单价”重新加入堆中重复此过程直到采购够n个单位。算法核心步骤结合示例拆解先梳理示例中的供应商筛选有效供应商忽略单价过高、库存为0的干扰项供应商A基础单价9元库存2性价比最高供应商B基础单价10元库存3供应商C基础单价10元库存1供应商D基础单价10元库存3供应商E基础单价100元库存200单价过高初期不考虑采购目标n4个单位逐步拆解每一步初始化最小堆将所有供应商的基础单价库存加入堆中堆顶为当前最低价9元供应商A。第1次采购取堆顶9元库存2花费9采购数量count1。供应商A库存剩余1下一个单价变为9110元将10元1重新加入堆中。第2次采购堆顶变为10元供应商A花费10累计19采购数量count2。供应商A库存耗尽不再加入堆中。第3次采购堆顶为10元供应商B/C/D均可此处选B花费10累计29采购数量count3。供应商B库存剩余2下一个单价变为10111元将11元2重新加入堆中。第4次采购堆顶仍为10元供应商C花费10累计39采购数量count4达到目标停止采购。最终总花费39元与示例输出一致验证了算法的正确性。四、算法伪代码通用版伪代码清晰梳理逻辑适配任何类似输入场景# 1. 初始化最小堆heap空最小堆for每个(base_price,stock)in供应商列表:ifstock0:# 只加入有库存的供应商heappush(heap,(base_price,stock))# 2. 初始化总花费和采购计数total_cost0# 总花费purchase_count0# 已采购数量# 3. 循环采购直到够n个或无供应商可采购whileheap 不为空 且 purchase_countn:# 取出当前最便宜的材料堆顶元素current_price,current_stockheappop(heap)# 采购1个单位total_costcurrent_price purchase_count1# 若该供应商还有库存涨价后重新加入堆ifcurrent_stock1:heappush(heap,(current_price1,current_stock-1))# 4. 返回总花费returntotal_cost五、复杂度分析为什么这个算法高效算法的效率主要取决于堆操作的时间复杂度我们来拆解一下初始化堆遍历所有供应商共M个供应商时间复杂度O(M log M)每次入堆操作是O(log M)。采购循环共执行n次每次循环包含1次出堆O(log M)和最多1次入堆O(log M)总时间复杂度O(n log M)。整体时间复杂度为O(M log M n log M)其中M是供应商数量n是采购数量。在实际场景中n和M通常不会特别大这个算法的效率完全够用属于最优解决方案。六、Python代码实现可直接运行结合示例输入写出可直接运行的代码方便大家调试和复用importheapqdefmin_purchase_cost(suppliers,n):# 初始化最小堆过滤掉库存为0的供应商heap[]forprice,stockinsuppliers:ifstock0:heapq.heappush(heap,(price,stock))total0count0whileheapandcountn:current_price,current_stockheapq.heappop(heap)# 采购1个totalcurrent_price count1# 库存剩余涨价后入堆ifcurrent_stock1:heapq.heappush(heap,(current_price1,current_stock-1))returntotal# 示例输入suppliers[[100,200],[9,2],[10,3],[10,1],[10,3]]n4# 调用函数输出结果print(min_purchase_cost(suppliers,n))# 输出39七、总结与拓展这道题的核心是“贪心策略”的应用——每一步都追求局部最优最终实现全局最优。而最小堆则是贪心策略的“好帮手”帮我们高效获取当前最优解避免了暴力遍历的低效。拓展思考如果题目新增限制比如每个供应商最多采购k个单位、采购有运输成本等只需在入堆、出堆时增加对应判断核心逻辑依然是“贪心最小堆”可见这种思路的通用性。其实算法并不难关键是找到“局部最优”的切入点再用合适的数据结构比如这里的最小堆提升效率。希望这篇解析能帮大家理清思路下次遇到类似的最优分配问题能快速想到对应的解决方案
