2026-09-06：购买最多物品数目Ⅰ。用go语言，你有一份商品目录，每件商品都对应一个“特征数值”和一个“售价”，同时你有一个总预算上限

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。

一、准备阶段

1. 1. 输入商品列表items和预算budget。

2. 2. 创建一个长度为budget + 1的数组f，全部初始化为 0，该数组用于动态规划（DP），f[j]表示恰好花费 j 元时，通过“首次购买”某些商品所能获得的最大物品总数（包括这些首次购买的商品本身以及由它们触发的所有免费赠品）。

3. 3. 设定一个变量minPrice，初始值为极大整数，用于记录所有商品中的最低价格。

对列表中的每一种商品p（即每一个不同种类）执行以下操作：

1. 1. 取出该商品的特征值factor和售价price。

2. 2. 更新全局最低价格minPrice = min(minPrice, price)。

3. 3. 统计该商品作为“首次购买”时能带来多少物品（包括自己）：

• • 遍历所有商品q，如果q的特征值能够被factor整除（即q[0] % factor == 0），则计数器cnt加一。

• • 因为自身特征值一定整除自身，所以cnt至少为 1。

4. 将该商品视为一个“捆绑包”：

• • 花费为price（购买它所需的钱）。

• • 价值为cnt（购买这一次后，你手上立即增加的商品数量，包含购买的那一件和所有由此触发的免费品）。

• • 由于重复购买同一商品不会再次触发赠品，因此每个“捆绑包”最多只能被选择一次（即每种商品最多首次购买一次）。

5. 使用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

• • 遍历商品：

• • • 商品0（factor=6, price=2）：能被6整除的只有自身（6），所以cnt=1，背包更新。

  • • 商品1（factor=2, price=6）：能被2整除的有6,2,3（三个），所以cnt=3，背包更新。

  • • 商品2（factor=3, price=4）：能被3整除的有6,3（两个），所以cnt=2，背包更新。

• • 背包计算后，例如花费8元可以选商品0（2元）和商品2（4元）共6元？实际最优可能是花费8元选商品0两次？但代码限制每种最多一次，所以选商品0（2元，cnt=1）和商品2（4元，cnt=2）共6元得3个，剩余3元买一个最便宜（2元）得1个，总计4个；或者选商品1（6元，cnt=3）加商品0（2元，cnt=1）共8元得4个，剩余1元不能买，得4个，结果正确。

• •时间复杂度：
  外层遍历所有商品，次数为n（n = len(items)）。
  内层统计cnt需要扫描所有商品，耗时 O(n)。
  背包更新遍历金额从budget到price，最多 O(budget)。
  因此总时间复杂度为O(n² + n·budget)。
  在本题约束下（n ≤ 1000，budget ≤ 1500），该复杂度可行。

• •额外空间复杂度：
  主要使用长度为budget + 1的 DP 数组，以及少量临时变量，因此额外空间复杂度为O(budget)。

package main

 import (
    "fmt"
    "math"
)

 func maximumSaleItems(items [][]int, budget int) (ans int) {
    f := make([]int, budget+1)
    minPrice := math.MaxInt

     for _, p := range items {
        factor, price := p[0], p[1]
        minPrice = min(minPrice, price)

         cnt := 0 // 统计 factor 的倍数（包括 factor）
        for _, q := range items {
            if q[0]%factor == 0 {
                cnt++
            }
        }

         // 视作一个体积为 price，价值为 cnt 的物品
        for j := budget; j >= price; j-- {
            f[j] = max(f[j], f[j-price]+cnt)
        }
    }

     for i, cnt := range f {
        ans = max(ans, cnt+(budget-i)/minPrice)
    }
    return
}

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

Python完整代码如下：

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

 from typing import List

 def maximumSaleItems(items: List[List[int]], budget: int) -> int:
    # 记录所有物品中的最低价格，用于最后填满剩余预算
    min_price = min(price for _, price in items)
    # dp[j] 表示花费恰好为 j 时，通过购买“有价值的物品”（每类最多买一次）能获得的最大数量
    dp = [0] * (budget + 1)
    for factor, price in items:
        # 统计购买该物品后能免费获得（包括自身，因为购买本身也算一个）的物品总数
        cnt = sum(1 for f, _ in items if f % factor == 0)
        # 0/1 背包逆序更新
        for j in range(budget, price - 1, -1):
            if dp[j - price] + cnt > dp[j]:
                dp[j] = dp[j - price] + cnt
    # 枚举所有可能的花费 i，剩余预算全部用来购买最便宜的物品（这些额外购买不会带来免费物品）
    ans = 0
    for i in range(budget + 1):
        total = dp[i] + (budget - i) // min_price
        if total > ans:
            ans = total
    return ans

 if __name__ == "__main__":
    items = [[6, 2], [2, 6], [3, 4]]
    budget = 9
    print(maximumSaleItems(items, budget)) 

C++完整代码如下：

  

  

    


 using namespace std;

 int maximumSaleItems(vector 
 
 int 
 >>& items,  
 int 
  budget) { 
 
 
      
 int 
  n = items.size(); 
 
 
     vector< 
 int 
 > dp(budget +  
 1 
 ,  
 0 
 ); 
 
 
      
 int 
  minPrice = INT_MAX; 
 
 
 
 
      
 for 
  (auto& p : items) { 
 
 
          
 int 
  factor = p[ 
 0 
 ]; 
 
 
          
 int 
  price = p[ 
 1 
 ]; 
 
 
         minPrice = min(minPrice, price); 
 
 
 
 
          
 // 统计能被当前 factor 整除的物品数量（包括自身） 
 
 
          
 int 
  cnt =  
 0 
 ; 
 
 
          
 for 
  (auto& q : items) { 
 
 
              
 if 
  (q[ 
 0 
 ] % factor ==  
 0 
 ) { 
 
 
                 cnt++; 
 
 
             } 
 
 
         } 
 
 
 
 
          
 // 0/1 背包，逆序更新 
 
 
          
 for 
  ( 
 int 
  j = budget; j >= price; --j) { 
 
 
             dp[j] = max(dp[j], dp[j - price] + cnt); 
 
 
         } 
 
 
     } 
 
 
 
 
      
 int 
  ans =  
 0 
 ; 
 
 
      
 for 
  ( 
 int 
  i =  
 0 
 ; i <= budget; ++i) { 
 
 
         ans = max(ans, dp[i] + (budget - i) / minPrice); 
 
 
     } 
 
 
      
 return 
  ans; 
 
 
 } 
 
 
 
 
 int 
  main() { 
 
 
     vector 
 
 int 
 >> items = {{ 
 6 
 ,  
 2 
 }, { 
 2 
 ,  
 6 
 }, { 
 3 
 ,  
 4 
 }}; 
 
 
      
 int 
  budget =  
 9 
 ; 
 
 
      
 int 
  result = maximumSaleItems(items, budget); 
 
 
     cout << result << endl; 
 
 
      
 return 
   
 0 
 ; 
 
 
 } 
 
 
 
 

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