求满足最低X金币需求的最小成本组合算法指导

问题概述 #

• 核心需求：采购至少X金币，从不同经销商的商品中选择组合（必须整份购买，可重复购买同一款），找到满足金币总量≥X的最小成本方案
• 关键规则：
  1. 商品必须整份购买，不能拆分
  2. 允许重复购买同一商品
• 现存困境：该问题类似无界背包，但无金币购买上限，直接套用背包解法会得到未达需求的错误结果；暴力递增背包上限的方式性能极差，无法应对大规模输入

补充约束 #

• 目标金币量 n ≤ 1,000,000
• 商品数量 k ≤ 1,000
• 单商品最大金币量 m ≤ 10,000,000

示例场景 #

可选商品价格表 #

任务目标 #

需采购至少12,880金币，当前测试得到的较优组合为「2个item_4 + 1个item_5」，但无法确定是否为全局最优解

寻求支持 #

希望获取适用于该问题的小众算法方向指导，无需提供代码

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