Любой набор строк, которые складываются в целевое число

Question

У меня есть следующие данные в таблице ПРОДАЖ:

BillItemID    CustID    BillDate    Item    BillAmt
1001          1         09-10-01    Suit    $50.00
1002          1         09-10-01    Shirt   $20.00
1003          1         09-10-01    Pants   $20.00
1004          1         09-10-01    Tie      $5.00
1005          1         09-01-10    Tie      $5.00

Клиент № 1 теперь представляет платеж в размере 75,00 долларов США. Я хочу найти любой набор строк (мне все равно, какой набор), так что SUM (BillAmt) выбранных строк составляет $ 75,00. Кто-нибудь может предложить SQL-запрос, который будет делать это?

Я использую неясную нишевую базу данных под названием R: Base (хорошо, кто здесь old ?), Которая поддерживает большую часть синтаксиса SQL-92 и предлагает хранимые процедуры. Я должен иметь возможность использовать любой ответ SQL-92, который не использует специфичные для поставщика расширения в моем приложении.

Answer 1

Это разновидность проблемы ранца , и вы не собираетесь решать ее в SQL без большого количества процедурного кода. Для начала вам понадобится рекурсия, и большинство хранимых процедур SQL совсем не справляются с рекурсией.

Answer 2

Из-за сложности (это в значительной степени проблема с рюкзаком, о которой говорил У. Крейг Трейдер), я бы порекомендовал добавить столбец PaidAmt, который вы обновляете в соответствии с определенным вами приоритетом.

Из вашего примера, когда клиент заплатил 75,00 $ и предположил, что самый дорогой товар оплачивается первым:

BillItemID    CustID    BillDate    Item    BillAmt  PaidAmt
1001          1         09-10-01    Suit    $50.00   $50.00
1002          1         09-10-01    Shirt   $20.00   $20.00
1003          1         09-10-01    Pants   $20.00   $5.00
1004          1         09-10-01    Tie      $5.00   $0.00
1005          1         09-01-10    Tie      $5.00   $0.00

---

После еще нескольких копаний это проблема Subset Sum и NP-Complete. По ссылке определен «приблизительный» алгоритм.

Answer 3

попробуйте это:

Выберите * из продаж где custid = 1 группа по custid имея сумму (биллам) = 75