2026-09-07：购买最多物品数目Ⅱ。用go语言，有若干种物品，每种物品有两个属性：一个因子值和一个价格。每种物品都可以无限量购买，但总

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数组（长度 n+1），用来统计每个因子值出现的次数（因为因子范围是 1..n）。

• 找出所有物品中的最低价格minPrice，用于最后剩余预算的“最便宜物品”购买。

此时：

•cntFactor[f]= 因子为 f 的物品总个数。

•minPrice为全局最低价格。

步骤 2：计算每个物品能触发多少免费物品

代码中有一个关键判断：

if price >= minPrice*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？我们看代码：

ans += c * 2

这里其实暗含了假设：每一个购买的物品恰好带来 1 个免费物品（即sumCnt[price]固定为 1）？但事实并非如此，sumCnt[price]可能很大。 我们再看仔细：其实原代码逻辑可能是简化的，它把“买一个物品”当作“增加 2 个总数”（自己+一个免费），但实际上免费数量可能不只 1。 这是一个潜在错误，但如果我们按题目要求去理解，这个实现是不严谨的。 但按照题目描述和输入输出，我们只需要解释这个代码现在的逻辑。所以这里我们按代码实际运行来解析：

• • 它认为每个购买的物品，无论价格多少，都能且仅能带来 1 个免费物品（因为ans += c*2是 1个购买+1个免费）。
  这显然与题目中“一个物品 i 可能免费送多个不同 j”不符。
  不过我们按题目要求“根据代码描述过程”，就按这个逻辑说明。

• 然后预算减少，继续下一个价格。

步骤 5：剩余预算购买最便宜物品

• • 预算可能还有剩余，此时买最便宜的物品（价格minPrice），每个只需花minPrice，直接增加budget/minPrice个物品（全部是购买，没有免费，因为免费已经被前面的物品用完了？但按代码逻辑，这里不再考虑免费）。

• • 最终返回ans。

二、时间复杂度与空间复杂度

• •时间复杂度：

• • • 统计cntFactor和minPrice：O(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)（主要来自倍数求和 + 排序）。

• •额外空间复杂度：

• • •cntFactor：O(n)

  • •cntMulti：O(n)

  • •sumCnt：最多存储 n 个不同价格，O(n)

  • • 其他常数变量。

  • • 总空间：O(n)。

三、最终结论（按代码实际逻辑）

• • 代码会先过滤高价物品（price ≥ 2*minPrice），只考虑低价物品的免费贡献。

• • 对每个低价物品，计算它能免费赠送多少个其他物品（去重后汇总到价格维度）。

• • 然后按价格从低到高购买，但每个购买只增加 2 个物品（自己 + 1 个免费）。

• • 剩余钱全部买最便宜物品。

因此输出结果为 5，与示例相符（但背后的推理与题目原意有简化偏差）。

总结：

• 过程：统计因子频率 → 计算低价物品的免费数量 → 按价格贪心购买（每个购买固定带来 2 个物品）→ 剩余钱买最便宜物品。

• 时间复杂度：O(n log n)

• 额外空间复杂度：O(n)

Go完整代码如下：

package main

 import (
    "fmt"
    "maps"
    "math"
    "slices"
)

 func maximumSaleItems(items [][]int, budget int) (ans int) {
    n := len(items)
    cntFactor := make([]int, n+1)
    minPrice := math.MaxInt
    for _, p := range items {
        cntFactor[p[0]]++
        minPrice = min(minPrice, p[1])
    }
    cntMulti := make([]int, n+1)
    sumCnt := map[int]int{} // price -> 相同 price 的 cnt 之和

     for _, p := range items {
        factor, price := p[0], p[1]
        if price >= minPrice*2 {
            continue
        }

         if cntMulti[factor] == 0 { // 之前没有计算过
            for j := factor; j <= n; j += factor {
                cntMulti[factor] += cntFactor[j]
            }
        }

         cnt := cntMulti[factor] - 1 // factor 的倍数不包括该物品
        if cnt > 0 {
            sumCnt[price] += cnt
        }
    }

     for _, price := range slices.Sorted(maps.Keys(sumCnt)) {
        if budget < price { // 没钱了
            break
        }
        c := min(sumCnt[price], budget/price) // 该物品最多买 c 个
        budget -= price * c
        ans += c * 2
    }

     // 剩余的钱买最便宜的物品
    return ans + budget/minPrice
}

 func main() {
    items := [][]int{{1, 6}, {2, 4}, {3, 5}}
    budget := 19
    result := maximumSaleItems(items, budget)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

 from math import inf
from collections import defaultdict

 def maximum_sale_items(items, budget):
    n = len(items)
    cnt_factor = [0] * (n + 1)
    min_price = inf
    for factor, price in items:
        cnt_factor[factor] += 1
        min_price = min(min_price, price)
    cnt_multi = [0] * (n + 1)
    sum_cnt = defaultdict(int)  # price -> 相同 price 的 cnt 之和
    for factor, price in items:
        if price >= min_price * 2:
            continue
        if cnt_multi[factor] == 0:  # 之前没有计算过
            for j in range(factor, n + 1, factor):
                cnt_multi[factor] += cnt_factor[j]
        cnt = cnt_multi[factor] - 1  # factor 的倍数不包括该物品
        if cnt > 0:
            sum_cnt[price] += cnt
    ans = 0
    for price in sorted(sum_cnt.keys()):
        if budget < price:  # 没钱了
            break
        c = min(sum_cnt[price], budget // price)  # 该物品最多买 c 个
        budget -= price * c
        ans += c * 2
    # 剩余的钱买最便宜的物品
    return ans + budget // min_price

 if __name__ == "__main__":
    items = [[1, 6], [2, 4], [3, 5]]
    budget = 19
    result = maximum_sale_items(items, budget)
    print(result)

C++完整代码如下：

  

  

    


 using namespace std;

 int maximumSaleItems(vector 
 
 int 
 >>& items,  
 int 
  budget) { 
 
 
      
 int 
  n = items.size(); 
 
 
     vector< 
 int 
 > cntFactor(n +  
 1 
 ,  
 0 
 ); 
 
 
      
 int 
  minPrice = INT_MAX; 
 
 
 
 
      
 for 
  (auto& p : items) { 
 
 
         cntFactor[p[ 
 0 
 ]]++; 
 
 
         minPrice = min(minPrice, p[ 
 1 
 ]); 
 
 
     } 
 
 
 
 
     vector< 
 int 
 > cntMulti(n +  
 1 
 ,  
 0 
 ); 
 
 
      
 map 
 < 
 int 
 ,  
 int 
 > sumCnt;   
 // price -> 相同 price 的 cnt 之和 
 
 
 
 
      
 for 
  (auto& p : items) { 
 
 
          
 int 
  factor = p[ 
 0 
 ], price = p[ 
 1 
 ]; 
 
 
          
 if 
  (price >= minPrice *  
 2 
 ) { 
 
 
              
 continue 
 ; 
 
 
         } 
 
 
 
 
          
 if 
  (cntMulti[factor] ==  
 0 
 ) {   
 // 之前没有计算过 
 
 
              
 for 
  ( 
 int 
  j = factor; j <= n; j += factor) { 
 
 
                 cntMulti[factor] += cntFactor[j]; 
 
 
             } 
 
 
         } 
 
 
 
 
          
 int 
  cnt = cntMulti[factor] -  
 1 
 ;   
 // factor 的倍数不包括该物品 
 
 
          
 if 
  (cnt >  
 0 
 ) { 
 
 
             sumCnt[price] += cnt; 
 
 
         } 
 
 
     } 
 
 
 
 
      
 int 
  ans =  
 0 
 ; 
 
 
      
 for 
  (auto& [price, cnt] : sumCnt) { 
 
 
          
 if 
  (budget < price) {   
 // 没钱了 
 
 
              
 break 
 ; 
 
 
         } 
 
 
          
 int 
  c = min(cnt, budget / price);   
 // 该物品最多买 c 个 
 
 
         budget -= price * c; 
 
 
         ans += c *  
 2 
 ; 
 
 
     } 
 
 
 
 
      
 // 剩余的钱买最便宜的物品 
 
 
      
 return 
  ans + budget / minPrice; 
 
 
 } 
 
 
 
 
 int 
  main() { 
 
 
     vector 
 
 int 
 >> items = {{ 
 1 
 ,  
 6 
 }, { 
 2 
 ,  
 4 
 }, { 
 3 
 ,  
 5 
 }}; 
 
 
      
 int 
  budget =  
 19 
 ; 
 
 
      
 int 
  result = maximumSaleItems(items, budget); 
 
 
     cout << result << endl; 
 
 
      
 return 
   
 0 
 ; 
 
 
 } 
 
 
 
 

我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。