查询最小行数以匹配给定值阈值

Question

我想创建一个类似于收银机的查询。想象一个收银机，里面装满了不同大小的硬币。我想以尽可能少的硬币数量检索硬币的总价值。

鉴于此 table：

id	value
1	100
2	100
3	500
4	500
5	1000

我将如何查询以下行的列表：

总价值至少达到给定的阈值
具有最小超出值（超出阈值的值）
在尽可能少的行中

例如，如果我的阈值是 1050，这将是预期的结果：

id	value
1	100
5	1000

我正在使用 postgres 和 elixir/ecto。如果它可以在单个查询中完成很好，如果它需要一系列多个查询没问题。

Answer 1

我自己试了一下，使用了之前问题的答案：

Using ABS() to order by the closest value to the threshold

根据上面@TheImpaler 的评论，这会优先考虑最小行数而不是最小超额行数。这不是我想要的 100%，所以如果有人可以的话，欢迎改进，但如果不是，我认为这已经足够好了：

-- outer query selects all rows underneath the threshold
-- inner subquery adds a running total column
-- window function orders by the difference between value and threshold
SELECT
    *
FROM (
    SELECT
        i.*,
        SUM(i.value) OVER (
            ORDER BY
                ABS(i.value - $THRESHOLD),
                i.id
        ) AS total
    FROM
        inputs i
    ) t
WHERE
    t.total - t.value < $THRESHOLD;

查询最小行数以匹配给定值阈值

Query smallest number of rows to match a given value threshold

sql

postgresql

ecto