1

Есть определенная сумма, есть набор товара с различными ценами. Подскажите как найти любой набор товаров, чтобы их сумма составляла искомую сумму. Т.е нужно набрать товара точно на эту сумму, при этом цены отличаются и кол-во товара может быть произвольное. В какую сторону думать? Все данные выгребаются из sql базы, средствами php, т.е. у нас есть уже готовая выборка товаром с их ценой и кол-вом.

alexey romashev
  • 145
  • 1
    Товары штучные или, типа, развесного сахара-песка? :) – Harry Aug 06 '18 at 06:49
  • Насколько я помню, дискретная версия данной задачи - NP-полная, так что вроде как точное решение - только перебором... Оптимизация, я так понимаю, не интересует? (Типа - набрать еще и товаров побольше по количеству или по весу) – Harry Aug 06 '18 at 06:51
  • https://ru.stackoverflow.com/q/581668/194569 – Mike Aug 06 '18 at 06:58
  • @Harry, товары только штучные без веса, без разницы по идее какое кол-во, будет в итоге набрано товара, главное чтобы на нужную сумму. Но кол-во товара ограниченное, нужно ещё и это учитывать. – alexey romashev Aug 06 '18 at 07:04
  • 1
    Ну типичная NP-полная задача целочисленного линейного программирования... – Harry Aug 06 '18 at 07:12
  • Опросить мерчендайзера в магазине с товарами :) А вообще неплохо бы упомянуть в чем решать эту задачу, sql например.. – NewView Aug 06 '18 at 07:13
  • @NewView на php, есть выборка с товарами из базы, нужно с этой выборки выбрать товар на определенную сумму. – alexey romashev Aug 06 '18 at 07:14
  • @Harry NP-полная. я правильно понял, что по сути это перебор всех возможных комбинаций? Говорила мне мама, учи алгоритмы... – alexey romashev Aug 06 '18 at 07:15
  • Так и поправьте свой вопрос, что есть база, она в формате sql, надо разработать правильные запросы к этой базе.. пример полей этой базы, и ТД. PHP роли то не играет, sql зоветься из любой среды программирования – NewView Aug 06 '18 at 07:16
  • @NewView да, сейчас укажу этот момент – alexey romashev Aug 06 '18 at 07:17
  • Обычная задача о рюкзаке и иже с ними. Настоятельно рекомендую решать её на клиенте, а не на SQL-сервере. А заодно помнить, что в такой постановке - строгое равенство,- задача может и не иметь решения. – Akina Aug 06 '18 at 07:28

0 Answers0