Алгоритм для минимизации стоимости товаров от разных поставщиков, какие ресурсы изучить?
==========================================================================================

 Пытаюсь на коленке для себя написать небольшой проект, но в алгоритмах не слишком силен. Встал в тупик и интересуюсь в какую сторону копать.  

Задача:  

Есть некое колличество различных товаров, в моих тестовых данных это 87.  

Есть различные продавцы, которые продают эти товары. (В моих данных, 163) У каждого из них есть только некоторые из нужных товаров в наличии и различные цены + доставка.  

Нужно найти, у кого и какие товары заказать, чтобы получилось дешевле всего. Так, чтобы в итоге мы получили все нужные товары. Цену доставки можно считать постоянной.  

Примеры - у нас может быть один продавец, который продает все товары, но дороже чем остальные, у которых есть только часть товаров, мы можем заказать от разных продавцов, заплатив больше за доставку, но в итоге секономив засчет более низких цен. Или наоборот, у нас есть куча продавцов, которые продают по одному товару очень дешево, и один который продает все сразу, но дороже. Тогда мы можем заказать подороже, но секономив за счет того что доставку платим один раз.  

  

Уже какое-то время пытаюсь решить задачу в лоб, не то чтобы сильно нужно было, но просто самому уже интересно разобраться :)   

Пока что за вменяемое время получилось сделать только минимизацию колличества продавцов - делал из предположения, что разброс цен не сильный. Но быстро обнаружил, что у кого самый большой ассортимент - цены тоже самые большие, и получается так себе.  

Цены минимизировать тупым перебором пробовал - но тоже получается очень долго т.к. слишком много возможных комбинаций, даже если делать оптимизации, подсовывая в начало перебора "наиболее перспективных" продавцов и обрывая перебор, если текущая цена уже превысила минимально найденную.  

Уверен что на основе этого можно сделать быстрый поиск "достаточно оптимального" решения, если не перебирать все возможные комбинации, а останавливать это все через какое-то время, предполагая что с оптимальными продавцами в начале, мы за первые несколько проходов найдем приемлемое решение, а потом будем лишь в пустую бегать, выжимая оставшиеся копейки.  

  

Собственно задача звучит как что-то, что где-то уже пытались решить, просто я об этом не знаю :) Поэтому в первую очередь интересно если есть какие-то готовые решения\структуры данных, которые умеют делать это или похожее. Понимаю, что скорее всего нужно копать куда-то в сторону комбинаторики, но не знаю правильные слова чтобы спросить гугл :) 

 угу. вы на своем примере поняли почему жадные алгоритмы не работают и практически пришли к branch-and-bound. "достаточно неплохое" решение можно получить эвристиками, лучшее - только перебором (правда, не полным, но иногда весьма длительным т.к. надо доказать что это действительно лучшее решение).  

  

у вас задача о рюкзаке (наполнить рюкзак необходимым кол-вом товаров при условии минимизации общей цены).   

  

вот тут я даже набрасывал пример решения такого типа задач с использованием готовых солверов (модель у вас другая, но принцип тот-же): [Какие есть достойные альтернативы жадному алгоритму (greedy)?](https://qna.habr.com/q/796195#answer_1662825). По крайней мере там есть все ключевые слова чтоб понять что надо искать дальше  

  

(ну и да, это далеко не единственный способ решения, я просто ленивый и описать модель для мип солвера у меня выходит быстрее всего. [Илья Николаевский](http://qna.habr.com/user/wataru) и [Сергей Соколов](http://qna.habr.com/user/sergiks) смогут еще много интересного добавить) 

 Можно свести к линейному целочисленному программированию (linear integer programming).  

  

Индикаторные переменные (0 или 1) - покупаете ли вы этот товар у этого продавца (x\_ij).  

Еще переменные - платите ли этому продавцу за доставку (y\_j).  

  

Ограничения:   

  

y\_j >= x\_ij  

sum\_j (x\_ij) = 1  

  

Целевая функция - мнинимизировать затраты: sum\_ij x\_ij*c\_ij + sum\_j y\_j*d\_j   

  

Потом решать каким-либо солвером (есть куча быстрых библиотек).  

  

Еще можно всякие методы отжига или генетические алгоритмы использовать.  

  

Можно еще полный перебор с отсечениями. Очевидно, что если мы берем какое-то множество продавцов, то каждый из них должен иметь минимальную цену по какому-то товару. Это значит, что можно поддерживать текущие минимальные цены на все товары у выбранных продавцов (+бесконечность, если никто не продает этот товар). Вы можете брать какого-то продавца, только если его цена по какому-то товару меньше. Ну и всякие ранние выходы - если сумма минимальных цен вообще по всем + текущие траты за доставку выше оптимального пока что ответа, дальше добавлять продавцов смысла нет.