2026-09-06购买最多物品数目Ⅰ。用go语言你有一份商品目录每件商品都对应一个“特征数值”和一个“售价”同时你有一个总预算上限。所有商品的库存都是无限的你可以按需购买任意数量但所有购买开销的总和不能超过预算。在你掏钱购买某件商品后会触发一个赠品规则对于任何其他种类的商品只要你购买的那件商品的特征数值能够整除它的特征数值你就能免费得到一件该商品。但需要特别注意的是如果你反复购买同一种商品这种赠送效果并不会叠加每种购买过的商品只会触发一次赠品机会。此外赠品是可以重叠获得的。如果某件免费商品同时能被多种你实际购买过的商品触发赠送条件那么每触发一次你就能多免费获得一件同样的商品互不冲突。你的任务是在严格遵守预算的前提下通过合理安排购买计划最终让你手里拥有的商品总数量包括自己花钱买的以及所有通过规则免费获得的达到最多。请算出这个最大总数。1 items.length 1000。items[i] [factori, pricei]。1 factori, pricei 1500。1 budget 1500。输入 items [[6,2],[2,6],[3,4]], budget 9。输出 4。解释你可以购买 2 个物品 0 和 1 个物品 2总花费为 2 * 2 4 8不超过 budget 9。购买物品 2 可以免费获得 1 个物品 0因为 factor2 3 可以整除 factor0 6。你最终拥有 3 个购买的物品和 1 个免费物品总共 4 个物品。题目来自力扣3946。一、准备阶段输入商品列表items和预算budget。创建一个长度为budget 1的数组f全部初始化为 0该数组用于动态规划DPf[j]表示恰好花费 j 元时通过“首次购买”某些商品所能获得的最大物品总数包括这些首次购买的商品本身以及由它们触发的所有免费赠品。设定一个变量minPrice初始值为极大整数用于记录所有商品中的最低价格。二、遍历每种商品构造“捆绑包”对列表中的每一种商品p即每一个不同种类执行以下操作取出该商品的特征值factor和售价price。更新全局最低价格minPrice min(minPrice, price)。统计该商品作为“首次购买”时能带来多少物品包括自己遍历所有商品q如果q的特征值能够被factor整除即q[0] % factor 0则计数器cnt加一。因为自身特征值一定整除自身所以cnt至少为 1。将该商品视为一个“捆绑包”花费为price购买它所需的钱。价值为cnt购买这一次后你手上立即增加的商品数量包含购买的那一件和所有由此触发的免费品。由于重复购买同一商品不会再次触发赠品因此每个“捆绑包”最多只能被选择一次即每种商品最多首次购买一次。使用0/1 背包方式更新f数组对于预算j从budget倒序递减到price执行状态转移f[j] max(f[j], f[j - price] cnt)逆序保证每种商品最多被选一次。三、补足剩余预算当所有商品都被处理完后f数组已经记录了在任意花费i下挑选若干种商品各买一次所能获得的最大物品数含赠品。接下来考虑用剩余的钱购买更多商品这些额外购买不会产生新的免费赠品因为要么是重复购买已选过的种类要么购买未选过的种类但不会触发额外赠品——代码假设后续购买只增加购买数量而不附加免费。枚举所有可能的花费i从 0 到budget当前已得物品数为f[i]。剩余金额为budget - i这些钱全部用来购买单价最低的商品价格为minPrice每个花费minPrice只能获得 1 个物品因为重复购买不再赠送。因此总数为f[i] (budget - i) / minPrice整数除法。记录所有情况的最大值最终返回该最大值作为答案。四、举例验证以题目输入为例items [[6,2],[2,6],[3,4]],budget 9最低价格minPrice 2遍历商品商品0factor6, price2能被6整除的只有自身6所以cnt1背包更新。商品1factor2, price6能被2整除的有6,2,3三个所以cnt3背包更新。商品2factor3, price4能被3整除的有6,3两个所以cnt2背包更新。背包计算后例如花费8元可以选商品02元和商品24元共6元实际最优可能是花费8元选商品0两次但代码限制每种最多一次所以选商品02元cnt1和商品24元cnt2共6元得3个剩余3元买一个最便宜2元得1个总计4个或者选商品16元cnt3加商品02元cnt1共8元得4个剩余1元不能买得4个结果正确。五、时间与空间复杂度时间复杂度外层遍历所有商品次数为nn len(items)。内层统计cnt需要扫描所有商品耗时 O(n)。背包更新遍历金额从budget到price最多 O(budget)。因此总时间复杂度为O(n² n·budget)。在本题约束下n ≤ 1000budget ≤ 1500该复杂度可行。额外空间复杂度主要使用长度为budget 1的 DP 数组以及少量临时变量因此额外空间复杂度为O(budget)。Go完整代码如下packagemainimport(fmtmath)funcmaximumSaleItems(items[][]int,budgetint)(ansint){f:make([]int,budget1)minPrice:math.MaxIntfor_,p:rangeitems{factor,price:p[0],p[1]minPricemin(minPrice,price)cnt:0// 统计 factor 的倍数包括 factorfor_,q:rangeitems{ifq[0]%factor0{cnt}}// 视作一个体积为 price价值为 cnt 的物品forj:budget;jprice;j--{f[j]max(f[j],f[j-price]cnt)}}fori,cnt:rangef{ansmax(ans,cnt(budget-i)/minPrice)}return}funcmain(){items:[][]int{{6,2},{2,6},{3,4}}budget:9result:maximumSaleItems(items,budget)fmt.Println(result)}Python完整代码如下# -*-coding:utf-8-*-fromtypingimportListdefmaximumSaleItems(items:List[List[int]],budget:int)-int:# 记录所有物品中的最低价格用于最后填满剩余预算min_pricemin(pricefor_,priceinitems)# dp[j] 表示花费恰好为 j 时通过购买“有价值的物品”每类最多买一次能获得的最大数量dp[0]*(budget1)forfactor,priceinitems:# 统计购买该物品后能免费获得包括自身因为购买本身也算一个的物品总数cntsum(1forf,_initemsiff%factor0)# 0/1 背包逆序更新forjinrange(budget,price-1,-1):ifdp[j-price]cntdp[j]:dp[j]dp[j-price]cnt# 枚举所有可能的花费 i剩余预算全部用来购买最便宜的物品这些额外购买不会带来免费物品ans0foriinrange(budget1):totaldp[i](budget-i)//min_priceiftotalans:anstotalreturnansif__name____main__:items[[6,2],[2,6],[3,4]]budget9print(maximumSaleItems(items,budget))C完整代码如下#includeiostream#includevector#includealgorithm#includeclimitsusingnamespacestd;intmaximumSaleItems(vectorvectorintitems,intbudget){intnitems.size();vectorintdp(budget1,0);intminPriceINT_MAX;for(autop:items){intfactorp[0];intpricep[1];minPricemin(minPrice,price);// 统计能被当前 factor 整除的物品数量包括自身intcnt0;for(autoq:items){if(q[0]%factor0){cnt;}}// 0/1 背包逆序更新for(intjbudget;jprice;--j){dp[j]max(dp[j],dp[j-price]cnt);}}intans0;for(inti0;ibudget;i){ansmax(ans,dp[i](budget-i)/minPrice);}returnans;}intmain(){vectorvectorintitems{{6,2},{2,6},{3,4}};intbudget9;intresultmaximumSaleItems(items,budget);coutresultendl;return0;}