多卖家多商品最优采购组合求解：替代暴力算法的最优方案

问题描述 #

需要采购4件指定商品，每件商品可从多个卖家处选择。要求：

• 若从某卖家采购商品，该卖家的累计采购金额必须达到指定最低额度（以获取免运费服务）；
• 当前采用暴力枚举所有可能的卖家组合，当商品数量或卖家数量增加时，计算耗时急剧上升，需寻找更高效的最优算法解决方案。

输入数据 #

{
   "items":[
      {
         "name":"item1",
         "sellers":[
            {
               "name":"seller5",
               "price":"37.89"
            },
            {
               "name":"seller3",
               "price":"5.44"
            },
            {
               "name":"seller10",
               "price":"53.66"
            },
            {
               "name":"seller1",
               "price":"32.63"
            },
            {
               "name":"seller9",
               "price":"13.30"
            },
            {
               "name":"seller7",
               "price":"80.81"
            },
            {
               "name":"seller6",
               "price":"67.70"
            }
         ]
      },
      {
         "name":"item2",
         "sellers":[
            {
               "name":"seller10",
               "price":"73.70"
            },
            {
               "name":"seller7",
               "price":"58.72"
            },
            {
               "name":"seller3",
               "price":"55.40"
            },
            {
               "name":"seller5",
               "price":"77.89"
            },
            {
               "name":"seller9",
               "price":"42.52"
            },
            {
               "name":"seller8",
               "price":"50.04"
            },
            {
               "name":"seller1",
               "price":"29.16"
            }
         ]
      },
      {
         "name":"item3",
         "sellers":[
            {
               "name":"seller8",
               "price":"91.76"
            },
            {
               "name":"seller2",
               "price":"42.48"
            },
            {
               "name":"seller3",
               "price":"59.96"
            },
            {
               "name":"seller7",
               "price":"98.46"
            },
            {
               "name":"seller9",
               "price":"31.96"
            },
            {
               "name":"seller6",
               "price":"23.28"
            }
         ]
      },
      {
         "name":"item4",
         "sellers":[
            {
               "name":"seller1",
               "price":"23.81"
            },
            {
               "name":"seller6",
               "price":"63.45"
            },
            {
               "name":"seller9",
               "price":"27.44"
            },
            {
               "name":"seller2",
               "price":"51.22"
            },
            {
               "name":"seller3",
               "price":"82.37"
            },
            {
               "name":"seller8",
               "price":"86.12"
            }
         ]
      }
   ]
}

高效替代方案 #

1. 分支定界法 #

这是暴力枚举的针对性优化，核心是提前砍掉无效路径：

• 预处理：给每件商品的卖家按价格从低到高排序，优先尝试低价组合，快速找到一个成本较低的初始最优解，为后续剪枝提供基准；
• 递归遍历：处理每件商品时，对每个可选卖家，计算当前路径的最小可能总成本（当前已花费成本 + 剩余商品的最低价格之和），如果该值大于当前最优解，直接放弃这条路径；
• 约束剪枝：每次选择卖家后，检查该卖家的累计金额：如果后续没有其他商品能从该卖家采购，且当前累计金额未达免运费额度，直接剪枝（这个组合无法满足免运费要求，无需继续遍历）。

2. 动态规划（DP） #

通过状态记录已选卖家的累计金额情况，只保留每个状态下的最小成本，避免重复计算：

• 状态定义：用哈希表存储状态，键是卖家-累计金额的映射（例如{'seller3': 61.34, 'seller9': 74.46}），值是达到该状态的最小总成本；
• 状态转移：处理第i件商品时，遍历当前所有状态，再遍历该商品的每个可选卖家：
  • 若卖家已在当前状态中，新的累计金额为原金额加当前商品价格，更新状态并保留最小总成本；
  • 若卖家不在当前状态中，新增该卖家的累计金额为当前商品价格，记录对应的总成本；
  • 对于同一组卖家的累计金额组合，只保留总成本最低的状态，减少冗余计算。

3. 整数规划建模（适合专业求解工具） #

如果可以使用商用或开源的规划求解器，将问题转化为整数线性规划模型，借助专业算法高效求解：

• 决策变量：
  • x[i][s]：0或1，表示是否为第i件商品选择卖家s；
  • y[s]：0或1，表示是否享受卖家s的免运费服务；
• 目标函数：最小化总采购成本 sum(x[i][s] * price[i][s])；
• 约束条件：
  • 每件商品必须选择一个卖家：sum(x[i][s] for s in 商品i的卖家列表) = 1，对所有商品i；
  • 若享受卖家s的免运费，累计采购金额需≥最低额度M：sum(x[i][s] * price[i][s]) ≥ M * y[s]，对所有卖家s；
  • 未从卖家s采购任何商品时，无法享受免运费：sum(x[i][s]) ≤ 4 * y[s]（4为商品总数，确保只有采购商品时y[s]才能为1）；
• 专业求解器会自动运用分支定界、割平面等高效算法处理，适合商品或卖家数量较多的场景。

内容的提问来源于stack exchange，提问作者DebuggingUnicorn