@hypertonyc

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

Есть таблица, один из столбцов ("amount") хранит значения целочисленного типа. Можно ли хитро написать селект, чтоб выбрать строки (order by created_at) таким образом, чтоб суммарное значение всех amount'ов было либо равно, либо максимально близко к заданному значению, но не превышало его? СУБД Postgresql 9.6
P.S.
Немного внесу ясности, нужно не выбрать из всех имеющихся строк комбинацию из подходящих значений, чтоб максимально приблизиться к нужному значению, а идти по порядку и складывать значения, пока не упрёмся в лимит. Сейчас так и работает: выбираются все значения в нужном порядке, а затем в цикле идём по строкам и наращиваем счётчик на amount, пока он не превысит нужное нам значение. Просто думал можно будет на уровне запроса выбрать необходимые строки.
  • Вопрос задан
  • 276 просмотров
Решения вопроса 1
Вроде так должно сработать
SELECT *
FROM (
  SELECT *,
    SUM(amount) OVER (ORDER BY created_at) AS sum_amount
  FROM таблица
) t
WHERE t.sum_amount <= ?;
Ответ написан
Пригласить эксперта
Ответы на вопрос 3
vesper-bot
@vesper-bot
Любитель файрволлов
Вообще, это частный случай задачи о рюкзаке, и одним запросом SQL заведомо не решается.
Ответ написан
Комментировать
Rsa97
@Rsa97
Для правильного вопроса надо знать половину ответа
Если не ошибаюсь, то это вариант задачи об упаковке рюкзака. Она относится к NP-полным и гарантированно решается только полным перебором вариантов. Вряд ли на SQL можно достаточно эффективно её решить, тем более одним запросом.
Ответ написан
Kwisatz
@Kwisatz
Больше web-приложений, хороших и разных
Window functions?
А, прошу прощения, выше уже отписали)
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы