基于PostgreSQL与Ecto实现类收银机逻辑的最优行查询：满足阈值且行数最少、超额最小

嘿，这个问题挺有意思的——本质是个带双重约束的组合优化问题：先用最少的硬币数量凑够（或超过）阈值，再在这个前提下让超额的部分尽可能小。结合你用的PostgreSQL和Ecto，我来给你一步步拆解解决方案。

核心思路 #

我们的优先级要明确：

1. 第一优先级：选中的硬币数量（行数）最少
2. 第二优先级：总价值超出阈值的部分最小

直接枚举所有硬币组合显然不现实，但我们可以利用PostgreSQL的递归CTE（公共表表达式）来高效生成所有不重复的组合，再按优先级筛选出最优解，最后关联原表取出对应的行。

PostgreSQL单条查询实现 #

假设你的硬币表名为coins，我们可以用递归CTE生成所有合法组合，再筛选最优解：

WITH RECURSIVE coin_combinations AS (
    -- 基础情况：每个单独硬币作为初始组合
    SELECT
        id AS last_id,
        ARRAY[id] AS ids,
        value AS total_value,
        1 AS count
    FROM coins
    UNION ALL
    -- 递归步骤：只添加id更大的硬币，避免重复组合（比如[1,5]和[5,1]视为同一组合）
    SELECT
        c.id AS last_id,
        cc.ids || c.id AS ids,
        cc.total_value + c.value AS total_value,
        cc.count + 1 AS count
    FROM coin_combinations cc
    JOIN coins c ON c.id > cc.last_id
),
-- 筛选出总价值达标组合，计算超额值
valid_combinations AS (
    SELECT
        ids,
        total_value,
        count,
        total_value - 1050 AS excess
    FROM coin_combinations
    WHERE total_value >= 1050
),
-- 按优先级取最优组合：先看数量最少，再看超额最小
best_combination AS (
    SELECT ids
    FROM valid_combinations
    ORDER BY count ASC, excess ASC
    LIMIT 1
)
-- 取出最优组合对应的硬币行
SELECT c.id, c.value
FROM coins c
JOIN best_combination bc ON c.id = ANY(bc.ids)
ORDER BY c.id;

用你给出的测试数据（阈值1050）运行这个查询，会精准返回id为1和5的两行，和预期结果一致。

Ecto框架下的实现 #

Ecto对复杂递归CTE的支持有限，所以最直接的方式是执行原生SQL，同时适配动态传入的阈值：

def get_best_coin_combination(repo, threshold) do
  sql = """
  WITH RECURSIVE coin_combinations AS (
      SELECT
          id AS last_id,
          ARRAY[id] AS ids,
          value AS total_value,
          1 AS count
      FROM coins
      UNION ALL
      SELECT
          c.id AS last_id,
          cc.ids || c.id AS ids,
          cc.total_value + c.value AS total_value,
          cc.count + 1 AS count
      FROM coin_combinations cc
      JOIN coins c ON c.id > cc.last_id
  ),
  valid_combinations AS (
      SELECT
          ids,
          total_value,
          count,
          total_value - $1 AS excess
      FROM coin_combinations
      WHERE total_value >= $1
  ),
  best_combination AS (
      SELECT ids
      FROM valid_combinations
      ORDER BY count ASC, excess ASC
      LIMIT 1
  )
  SELECT c.id, c.value
  FROM coins c
  JOIN best_combination bc ON c.id = ANY(bc.ids)
  ORDER BY c.id;
  """

  repo.query!(sql, [threshold])
  |> Map.get(:rows)
  |> Enum.map(fn [id, value] -> %{id: id, value: value} end)
end

调用这个函数时，只需传入你的Repo实例和目标阈值即可。

注意事项 #

• 这个方法的时间复杂度是O(2^n)（n为硬币数量），所以当硬币数量超过20个时，性能会明显下降。如果你的硬币数据量很大，建议在应用层用动态规划算法处理，再回查数据库取对应行。
• 递归时通过c.id > cc.last_id避免重复组合，不会影响结果的正确性，只是减少不必要的计算。

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