Как выбрать из таблицы строки, чтоб сумма значений не превышала заданную величину?

Question

[hypertonyc]

Есть таблица, один из столбцов ("amount") хранит значения целочисленного типа. Можно ли хитро написать селект, чтоб выбрать строки (order by created_at) таким образом, чтоб суммарное значение всех amount'ов было либо равно, либо максимально близко к заданному значению, но не превышало его? СУБД Postgresql 9.6
P.S.
Немного внесу ясности, нужно не выбрать из всех имеющихся строк комбинацию из подходящих значений, чтоб максимально приблизиться к нужному значению, а идти по порядку и складывать значения, пока не упрёмся в лимит. Сейчас так и работает: выбираются все значения в нужном порядке, а затем в цикле идём по строкам и наращиваем счётчик на amount, пока он не превысит нужное нам значение. Просто думал можно будет на уровне запроса выбрать необходимые строки.

Answer 1

[Станислав Б]

Вроде так должно сработать

SELECT *
FROM (
  SELECT *,
    SUM(amount) OVER (ORDER BY created_at) AS sum_amount
  FROM таблица
) t
WHERE t.sum_amount <= ?;

Comments

[hypertonyc]

Извиняюсь, смотрю "на бегу". Походу оно самое! А почему нельзя просто?

SELECT
id,amount,created_at,
SUM(amount) OVER (ORDER BY created_at) AS sum_amount
FROM таблица ORDER BY created_at WHERE sum_amount <= ?;

[Станислав Б]

hypertonyc, Оконные функции считаются уже после фильтрации.

[hypertonyc]

Станислав Б, да.так и подумал. Спасибо!

Answer 2

[Максим Гришин]

Вообще, это частный случай задачи о рюкзаке, и одним запросом SQL заведомо не решается.

Answer 3

[Rsa97]

Если не ошибаюсь, то это вариант задачи об упаковке рюкзака. Она относится к NP-полным и гарантированно решается только полным перебором вариантов. Вряд ли на SQL можно достаточно эффективно её решить, тем более одним запросом.

Comments

[Станислав Б]

чтоб выбрать строки (order by created_at)

возможно автору нужно попроще и нужны просто строки по порядку, пока сумму не больше некого предела

[hypertonyc]

Станислав Б, именно

Answer 4

[Вячеслав Успенский]

Window functions?
А, прошу прощения, выше уже отписали)

Comments

[hypertonyc]

Угу, познакомился с оконными функциями. Новый день - новые открытия :)