2026-09-07购买最多物品数目Ⅱ。用go语言有若干种物品每种物品有两个属性一个因子值和一个价格。每种物品都可以无限量购买但总花费不能超过给定预算。购买之后可以获得额外的免费物品规则是如果你购买了某种物品 i那么对于每一种其他物品 j只要物品 i 的因子值能整除物品 j 的因子值你就能免费获得一个物品 j。对于每一对物品 i 和 j无论你购买了多少个物品 i最多只能因此免费获得一个物品 j。如果同一个物品 j 通过不同的已购物品 i 满足整除条件那么它可以被多次免费获得。目标是在总花费不超过预算的情况下使最终得到的物品总数最多这里的总数包括你花钱买的物品和所有免费获得的物品。1 items.length 100000。items[i] [factori, pricei]。1 factori items.length。1 pricei 1000000000。1 budget 1000000000。输入 items [[1,6],[2,4],[3,5]], budget 19。输出 5。解释你可以购买 2 个物品 0 和 1 个物品 1总花费为 2 * 6 4 16不超过 budget 19。购买的其中 1 个物品 0 可以免费获得 1 个物品 1因为 factor0 1 可以整除 factor1 2。购买的另一个物品 0 可以免费获得 1 个物品 2因为 factor0 1 可以整除 factor2 3。你最终拥有 3 个购买的物品和 2 个免费物品总共 5 个物品。题目来自力扣3947。一、代码设计思路分步骤详解步骤 1基本统计与预处理读取items数量记为n。创建cntFactor数组长度 n1用来统计每个因子值出现的次数因为因子范围是 1…n。找出所有物品中的最低价格minPrice用于最后剩余预算的“最便宜物品”购买。此时cntFactor[f] 因子为 f 的物品总个数。minPrice为全局最低价格。步骤 2计算每个物品能触发多少免费物品代码中有一个关键判断ifpriceminPrice*2{continue}这个条件的作用是如果一个物品的价格比最便宜物品的两倍还贵那么用它来触发免费可能不划算因为钱有限优先买便宜的物品更可能获得更高的购买数量并且同样可以触发免费。实际这里是一个优化剪枝避免计算高价格物品的免费贡献因为它们的价格太高不可能在最优解中被购买因为买一个贵的能换来的免费数最多只是倍数关系而买便宜的还能多买几个总收益更大。然后对价格低于2*minPrice的物品才计算它能够触发多少免费物品。步骤 3计算每个“可购买物品”能带来的免费数量对于这样的物品 p因子 factor价格 price如果之前没有计算过这个 factor 的免费数量通过cntMulti[factor]是否为 0 判断则计算遍历所有 factor 的倍数j factor, 2*factor, ..., n将cntFactor[j]累加起来。结果 所有因子为 factor 倍数的物品的总数量。这个值存入cntMulti[factor]。然后cnt cntMulti[factor] - 1减去 1 是因为不能免费获得自己物品 j 必须“其他物品”。如果cnt 0那么该物品价格 price 对应的“可获得的免费数量”增加 cnt。注意这里用sumCnt[price] cnt因为可能存在多个不同 factor 但价格相同的物品它们都贡献免费数量要汇总。重点理解这里cntMulti[factor]表示如果你买了一个因子为 factor 的物品总共能免费获得多少个其他物品。汇总到sumCnt[price]意思是花 price 购买一个物品能带来多少免费物品这些免费物品来自于所有符合条件的因子倍数关系。步骤 4按价格从小到大考虑购买对sumCnt的所有价格进行升序排序。遍历每个价格price如果预算已经不够买这个价格的一个物品就结束因为价格排序是升序后面的更贵。否则计算在当前预算下最多能买多少个该价格的物品c min(sumCnt[price], budget/price)。这里为什么要取 min因为sumCnt[price]是该价格物品能提供的最大免费总数但实际买太多可能用不完这些免费名额因为免费物品本身是固定种类的买了 10 个同因子物品每个 j 依然只能送一次所以免费总数有限所以要限制购买数量不超过它能提供的免费总数否则多买的浪费钱且无额外收益。买 c 个花费price*c增加购买数 c同时每个购买的物品带来sumCnt[price]个免费物品注意这里的逻辑实际上每个该价格的物品都能带来相同的免费数量因为因子相同或者不同因子但价格相同可能免费数不同但这里假设它们合并后每个都能提供同样多的免费其实这里代码将相同价格的不同因子物品的免费总数累加然后每个购买都按这个总数来算这其实是一个近似优化因为不同因子带来的免费数可能不同但代码认为价格相同即可等价处理。因此总物品增加 c购买 c * sumCnt[price]免费但注意这里代码写的是ans c*2我们看代码ansc*2这里其实暗含了假设每一个购买的物品恰好带来 1 个免费物品即sumCnt[price]固定为 1但事实并非如此sumCnt[price]可能很大。我们再看仔细其实原代码逻辑可能是简化的它把“买一个物品”当作“增加 2 个总数”自己一个免费但实际上免费数量可能不只 1。这是一个潜在错误但如果我们按题目要求去理解这个实现是不严谨的。但按照题目描述和输入输出我们只需要解释这个代码现在的逻辑。所以这里我们按代码实际运行来解析它认为每个购买的物品无论价格多少都能且仅能带来 1 个免费物品因为ans c*2是 1个购买1个免费。这显然与题目中“一个物品 i 可能免费送多个不同 j”不符。不过我们按题目要求“根据代码描述过程”就按这个逻辑说明。然后预算减少继续下一个价格。步骤 5剩余预算购买最便宜物品预算可能还有剩余此时买最便宜的物品价格minPrice每个只需花minPrice直接增加budget/minPrice个物品全部是购买没有免费因为免费已经被前面的物品用完了但按代码逻辑这里不再考虑免费。最终返回ans。二、时间复杂度与空间复杂度时间复杂度统计cntFactor和minPriceO(n)计算每个物品的免费数量时每个因子最多被计算一次cntMulti[factor]只算一次而每个因子计算需要遍历它的倍数总次数为 n/1 n/2 … n/n ≈ n log n。排序sumCnt的 key假设不同价格种类数为 k则 O(k log k)k ≤ n。遍历价格处理O(k)。总复杂度O(n log n)主要来自倍数求和 排序。额外空间复杂度cntFactorO(n)cntMultiO(n)sumCnt最多存储 n 个不同价格O(n)其他常数变量。总空间O(n)。三、最终结论按代码实际逻辑代码会先过滤高价物品price ≥ 2*minPrice只考虑低价物品的免费贡献。对每个低价物品计算它能免费赠送多少个其他物品去重后汇总到价格维度。然后按价格从低到高购买但每个购买只增加 2 个物品自己 1 个免费。剩余钱全部买最便宜物品。因此输出结果为 5与示例相符但背后的推理与题目原意有简化偏差。总结过程统计因子频率 → 计算低价物品的免费数量 → 按价格贪心购买每个购买固定带来 2 个物品→ 剩余钱买最便宜物品。时间复杂度O(n log n)额外空间复杂度O(n)Go完整代码如下packagemainimport(fmtmapsmathslices)funcmaximumSaleItems(items[][]int,budgetint)(ansint){n:len(items)cntFactor:make([]int,n1)minPrice:math.MaxIntfor_,p:rangeitems{cntFactor[p[0]]minPricemin(minPrice,p[1])}cntMulti:make([]int,n1)sumCnt:map[int]int{}// price - 相同 price 的 cnt 之和for_,p:rangeitems{factor,price:p[0],p[1]ifpriceminPrice*2{continue}ifcntMulti[factor]0{// 之前没有计算过forj:factor;jn;jfactor{cntMulti[factor]cntFactor[j]}}cnt:cntMulti[factor]-1// factor 的倍数不包括该物品ifcnt0{sumCnt[price]cnt}}for_,price:rangeslices.Sorted(maps.Keys(sumCnt)){ifbudgetprice{// 没钱了break}c:min(sumCnt[price],budget/price)// 该物品最多买 c 个budget-price*c ansc*2}// 剩余的钱买最便宜的物品returnansbudget/minPrice}funcmain(){items:[][]int{{1,6},{2,4},{3,5}}budget:19result:maximumSaleItems(items,budget)fmt.Println(result)}Python完整代码如下# -*-coding:utf-8-*-frommathimportinffromcollectionsimportdefaultdictdefmaximum_sale_items(items,budget):nlen(items)cnt_factor[0]*(n1)min_priceinfforfactor,priceinitems:cnt_factor[factor]1min_pricemin(min_price,price)cnt_multi[0]*(n1)sum_cntdefaultdict(int)# price - 相同 price 的 cnt 之和forfactor,priceinitems:ifpricemin_price*2:continueifcnt_multi[factor]0:# 之前没有计算过forjinrange(factor,n1,factor):cnt_multi[factor]cnt_factor[j]cntcnt_multi[factor]-1# factor 的倍数不包括该物品ifcnt0:sum_cnt[price]cnt ans0forpriceinsorted(sum_cnt.keys()):ifbudgetprice:# 没钱了breakcmin(sum_cnt[price],budget//price)# 该物品最多买 c 个budget-price*c ansc*2# 剩余的钱买最便宜的物品returnansbudget//min_priceif__name____main__:items[[1,6],[2,4],[3,5]]budget19resultmaximum_sale_items(items,budget)print(result)C完整代码如下#includeiostream#includevector#includemap#includealgorithm#includeclimitsusingnamespacestd;intmaximumSaleItems(vectorvectorintitems,intbudget){intnitems.size();vectorintcntFactor(n1,0);intminPriceINT_MAX;for(autop:items){cntFactor[p[0]];minPricemin(minPrice,p[1]);}vectorintcntMulti(n1,0);mapint,intsumCnt;// price - 相同 price 的 cnt 之和for(autop:items){intfactorp[0],pricep[1];if(priceminPrice*2){continue;}if(cntMulti[factor]0){// 之前没有计算过for(intjfactor;jn;jfactor){cntMulti[factor]cntFactor[j];}}intcntcntMulti[factor]-1;// factor 的倍数不包括该物品if(cnt0){sumCnt[price]cnt;}}intans0;for(auto[price,cnt]:sumCnt){if(budgetprice){// 没钱了break;}intcmin(cnt,budget/price);// 该物品最多买 c 个budget-price*c;ansc*2;}// 剩余的钱买最便宜的物品returnansbudget/minPrice;}intmain(){vectorvectorintitems{{1,6},{2,4},{3,5}};intbudget19;intresultmaximumSaleItems(items,budget);coutresultendl;return0;}