LeetCode-Go 题解 638Shopping Offers 大礼包最优组合的 DFS 剪枝实现【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读LeetCode-Go 仓库以「一题一目录、一题双文件解法 测试」的方式沉淀了数百道 LeetCode 的 Go 题解本题解对应其中 leetcode/0638.Shopping-Offers。638. Shopping Offers 是一道中等偏难的「组合优化」题目商店里每种商品有单价同时提供若干可无限次购买的大礼包要求恰好购买完购物清单上的数量求最低花费。读完本文你将掌握如何用状态化 DFS 枚举「买礼包 / 跳过礼包 / 按单价补齐」三种购买决策以及如何用「不允许超出清单数量」这一约束完成关键剪枝并能在本地直接运行仓库内附带的测试用例验证结论。题目原文In LeetCode Store, there are some kinds of items to sell. Each item has a price.However, there are some special offers, and a special offer consists of one or more different kinds of items with a sale price.You are given the each items price, a set of special offers, and the number we need to buy for each item. The job is to output the lowest price you have to pay forexactlycertain items as given, where you could make optimal use of the special offers.Each special offer is represented in the form of an array, the last number represents the price you need to pay for this special offer, other numbers represents how many specific items you could get if you buy this offer.You could use any of special offers as many times as you want.题目大意在 LeetCode 商店中有许多在售的物品。然而也有一些大礼包每个大礼包以优惠的价格捆绑销售一组物品。现给定每个物品的价格、每个大礼包包含物品的清单以及待购物品清单请输出确切完成待购清单的最低花费。每个大礼包由一个数组描述最后一个数字代表大礼包的价格其他数字分别表示内含的其他种类物品的数量。任意大礼包可无限次购买。输入输出模型题目输入由三个数组组成以 Go 的参数形式呈现与仓库中 解法文件 的函数签名一致参数类型含义price[]int每种物品的单价price[i]表示第 i 种物品的价格special[][]int大礼包集合每个礼包数组的前len(price)个元素是该礼包内含的各物品数量最后一个元素是该礼包的售价needs[]int待购清单needs[i]表示需要购买第 i 种物品的数量返回值int恰好买齐清单上所有物品所需的最低花费。约束条件最多 6 种物品len(price) 6最多 100 个大礼包对每种物品最多只需要购买 6 个needs[i] 6不允许购买超出待购清单数量的物品即使这样总价更低也不行这是本题唯一的硬性限制也是剪枝的核心依据。示例详解示例 1Input: [2,5], [[3,0,5],[1,2,10]], [3,2] Output: 14有 A、B 两种物品价格分别为 ¥2 和 ¥5大礼包 1支付 ¥5 可得 3A 和 0B大礼包 2支付 ¥10 可得 1A 和 2B待购清单3A 和 2B。最优方案购买 1 次大礼包 2¥10得到 1A、2B剩余 2A 按单价补齐¥2 × 2 ¥4合计¥14。示例 2Input: [2,3,4], [[1,1,0,4],[2,2,1,9]], [1,2,1] Output: 11A、B、C 的价格分别为 ¥2、¥3、¥4大礼包 1¥4 得 1A、1B大礼包 2¥9 得 2A、2B、1C待购清单1A、2B、1C。最优方案购买 1 次大礼包 1¥4得到 1A、1B剩余 1B 按单价补齐¥31C 按单价补齐¥4合计¥11。注意大礼包 2 只需 ¥9 就能拿到 2A、2B、1C看似更划算但它会多买出 1 个 A违反了「不能超出清单数量」的约束因此不可取——这正是本题与一般「背包 优惠」题目的关键差异。解题思路状态化 DFS 与三分支枚举这一题可以用 DFS 暴力解答也可以用 DP动态规划求解仓库题解采用DFS 剪枝的方案。核心思路如下状态定义设当前搜索状态为dfs(price, special, needs, pay)其中price、special为题目给定的单价与礼包集合全程不变仅special通过切片缩减遍历范围needs为当前仍需购买的每种物品数量pay为截至当前状态已经累计支付的金额。三种购买决策对应三种 DFS 分支。针对当前遍历到的礼包选当前礼包礼包内含数量从needs中对应扣减pay累加该礼包售价继续递归礼包可无限次使用因此下一层仍然从当前礼包开始考虑跳过当前礼包保持needs与pay不变转而考察下一个礼包对应special[1:]不使用任何礼包全部按单价补齐这是搜索树的叶子结算分支把剩余needs[i]全部乘以price[i]累加进pay得到一个完整方案的总花费。当所有分支遍历完毕全局最小值即题目所求。关键剪枝是否需要继续买礼包必须以「不超出清单数量」为前提。进入每层递归时先检查needs若某一维needs[i] 0说明此前选择礼包已经超买该分支立即返回不合题意若needs全为 0说明清单已恰好完成无需再买直接按单价补齐补齐量为 0结算即可只有当needs中存在正值且仍有礼包可选时才继续展开三分支。从源码结构看这种「先校验再递归」的顺序保证了任何产生负数的分支都不会继续扩散从而把搜索树限制在needs各维度 06 的有限网格内。仓库源码实现与逐段拆解以下代码与仓库 638. Shopping Offers.go 完全一致并补充了逐行注释func shoppingOffers(price []int, special [][]int, needs []int) int { res : -1 // -1 作为「尚未找到任何可行方案」的哨兵值 dfsShoppingOffers(price, special, needs, 0, res) return res } func dfsShoppingOffers(price []int, special [][]int, needs []int, pay int, res *int) { noNeeds : true // 剪枝若某一种商品的需求被扣成负数说明礼包买超了此路不通 for _, need : range needs { if need 0 { return } if need ! 0 { noNeeds false } } // 叶子结算礼包用完special 为空或清单已满足noNeeds时 // 把剩余需求按单价补齐累加得到一种完整方案的花费 if len(special) 0 || noNeeds { for i, p : range price { pay (p * needs[i]) } if pay *res || *res -1 { *res pay } return } // 分支 1 2选择当前礼包。复制一份 needs 并扣减礼包内含数量 newNeeds : make([]int, len(needs)) copy(newNeeds, needs) for i, n : range newNeeds { newNeeds[i] n - special[0][i] } // 分支 1买当前礼包礼包仍可继续购买special 不缩减支付累加礼包售价 dfsShoppingOffers(price, special, newNeeds, payspecial[0][len(price)], res) // 分支 2买当前礼包但下次不再考虑它special[1:]避免重复枚举同一礼包组合 dfsShoppingOffers(price, special[1:], newNeeds, payspecial[0][len(price)], res) // 分支 3不买当前礼包直接跳过special[1:]需求与支付均不变 dfsShoppingOffers(price, special[1:], needs, pay, res) }实现细节要点special[0][len(price)]通过「礼包数组长度 物品种类数 1」的固定格式取到礼包售价与题目描述严格对应每次展开分支前用make copy复制needs保证三个分支各自持有独立的状态切片互不污染res以指针传递所有递归分支共享同一个结果变量叶子节点直接更新全局最优分支 1 与分支 2 的差异在于special是否缩减分支 1 允许同一礼包被连续多次购买分支 2 与分支 3 负责推进礼包指针二者合起来覆盖了「任意礼包可无限次购买」的全部组合空间。测试用例与本地验证仓库为本题提供了配套测试 638. Shopping Offers_test.go使用标准的 table-driven 风格定义para638含price、special、needs与ans638期望答案然后逐条断言shoppingOffers的返回结果。测试覆盖了文档中的两个示例qs : []question638{ { para638{[]int{2, 5}, [][]int{{3, 0, 5}, {1, 2, 10}}, []int{3, 2}}, ans638{14}, }, { para638{[]int{2, 3, 4}, [][]int{{1, 1, 0, 4}, {2, 2, 1, 9}}, []int{1, 2, 1}}, ans638{11}, }, }在仓库根目录执行以下命令即可运行该测试Go 测试框架会自动匹配包内以_test.go结尾的文件go test -v ./leetcode/0638.Shopping-Offers/输出中【input】:[2 5] [[3 0 5] [1 2 10]] [3 2] 【output】:14对应示例 1 的验证【input】:[2 3 4] [[1 1 0 4] [2 2 1 9]] [1 2 1] 【output】:11对应示例 2 的验证。若想对全部题目做一次完整回归可参考仓库 gotest.sh 中给出的方式该脚本用-covermodeatomic -coverprofilecoverage.txt一次性汇总各包覆盖率go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...复杂度分析状态空间needs的每一维取值被限制在 06超买即剪枝因此有效状态数上界约为7^nn ≤ 6每个状态需要遍历至多 m 个礼包m ≤ 100展开分支并在叶子处做一次 O(n) 的单价补齐结算综合来看从算法结构上可推断其最坏复杂度约为O(m · 7^n)在题目给定的 n ≤ 6、m ≤ 100 的约束下完全可控空间复杂度为递归深度与每层needs副本之和即O(depth · n)。正因为「最多 6 种商品、每种最多 6 件」这一数据规模设计纯 DFS 才能在剪枝后高效求出最优解这也是本题选择暴力搜索而非复杂优化模型的原因。延伸思考DP 视角题解文档指出本题「也可以用 DP」。从状态结构看needs的 6 维坐标天然构成一个多维状态表可用记忆化搜索memo 化dfs(needs)消除重复子问题把指数级搜索收敛到多项式级感兴趣的读者可以沿此方向重构一版 DP 实现并对照测试用例验证结果一致。与完全背包的对比礼包可无限次购买形式上接近「完全背包」但额外多出「不允许超出容量清单数量」的约束因此既不能贪心选最便宜的礼包也不能容忍超买必须穷举所有不越界的组合。工程价值这种「有限状态 约束剪枝 全局最优指针」的 DFS 模板同样适用于组合优惠结算、凑单满减、资源打包采购等一类「恰好凑足需求的最小成本」问题。相关文件索引题解文档leetcode/0638.Shopping-Offers/README.mdGo 实现leetcode/0638.Shopping-Offers/638. Shopping Offers.go单元测试leetcode/0638.Shopping-Offers/638. Shopping Offers_test.go项目总览README.md含中英文题解索引与分类导航可定位到0600~0699区间继续阅读同类题目【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考