基于可重复数字列表的高效达标/超目标值组合算法求解

核心问题 #

给定可重复使用的数字列表和目标值，需找到总和≥目标值且最接近目标值的最优组合。现有基于余数的贪心思路存在局限，无法覆盖所有最优情况（如示例中目标值242、数字列表[40,100,240]的最优解100+4×40=260，就无法通过余数法得到）。

现有方法的局限 #

余数思路仅考虑“取最大商后补余数对应的数字”，但忽略了减少大数字的使用次数，用小数字组合填补差值可能得到更优结果。比如示例中，若固定100的使用次数为2，剩余42需要2个40补全；但将100的使用次数减为1，剩余142用4个40补全，总和会更接近目标值。

高效解决方向 #

不需要遍历所有可能的组合，以下几种方法可通过剪枝或动态规划高效找到最优解：

1. 剪枝回溯法 #

• 先将数字按从大到小排序，优先尝试大数字，快速得到一个较优的初始解（比如单一数字的最优解）。
• 回溯过程中记录当前找到的最小超目标总和：
  • 若当前路径的总和已超过这个最小值，直接终止该分支（剪枝）。
  • 若当前总和≥目标值，更新最小值并记录对应组合。
• 这种方法通过剪枝避免大量无效计算，适合数字数量较少的场景。

2. 动态规划法 #

• 定义状态dp[i]为达到或超过数值i所需的最小总和。
• 初始化：dp[0] = 0，其余dp[i]设为无穷大（表示初始不可达）。
• 状态转移：对每个数字num，遍历从num到target + max_num的范围（max_num是列表中的最大数字，因为超过目标值的部分最多无需超过一个最大数字，否则可替换为更小的组合），更新dp[i] = min(dp[i], dp[i - num] + num)。
• 最终dp[target]即为所求的最小总和，通过回溯可找到对应的数字组合。

3. 贪心+局部调整策略 #

• 先按贪心思路得到初始解：尽可能多取大数字，再用小数字补全余数。
• 对每个大数字，尝试减少其使用次数（从1到当前使用次数），计算剩余差值需要多少小数字补全（向上取整），得到新的总和，保留最小的那个。
• 比如示例中：
  • 初始贪心解：2×100 + 2×40 = 280
  • 调整100的数量为1：1×100 + ceil((242-100)/40)×40 = 100 + 4×40 = 260
  • 调整100的数量为0：0×100 + 7×40 = 280
  • 对比后得到最优解260
• 这种方法实现简单、效率较高，适合数字列表规模不大的场景。

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