поиск оптимальной суммы столбцов

[yurican]

Здравствуйте!
Готов заплатить электронными деньгами за хороший алгоритм
Пожалуйста, помогите со следующим алгоритмом:

Есть двумерный массив
price[id_postavshika][id_tovara] = цена
или
price[id_tovara][id_postavshika] = цена

выглядит это как таблица сравнения цен различных продавцов на схожие товары:
__________ тов1 _ тов2 _ тов3 _ тов4
продавец1 | 1000 | 2000 | 1500| 3040
продавец2 | 1200 | 1800 | 1600| 3000
продавец3 | 1000 | 2300 | 1900| 2950
продавец4 | 1300 | 1900 | 1700| 3100
продавец5 | 1200 | 2200 | 1900| 3150

Ситуация: мы покупаем все 4 товара.
Найти самого выгодного продавца не является проблемой (можно просто просуммировать столбцы и получить ИТОГО).
Найти список продавцов, чтобы ИТОГО получилось наименьшим, также не проблема.

ПРОБЛЕМА:
найти минимальную итоговую стоимость покупки, если покупать у:
* двух продавцов
* трёх продавцов
* четырёх продавцов

чето я голову сломал уже)

Найти список продавцов, чтобы ИТОГО получилось наименьшим, также не проблема.

не пойму как это отличается от вашей основной проблемы, но впрочем неважно

ПРОБЛЕМА:
найти минимальную итоговую стоимость покупки, если покупать у:
* двух продавцов
* трёх продавцов
* четырёх продавцов

алгоритм называется min-cost max-flow. строишь транспортную сеть - двудольный граф, с одной стороны продавцы, с другой - товары, соединяешь все пары ребрами соответствующих стоимостей, потом соединяешь ребра из товаров со стоком ребрами нулевой стоимости и пропускной способности, равной столько единиц товара нужно и запускаешь поток. пример реализации https://github.com/infnty/acm/blob/m...raphs/MCMF3.cc

Готов заплатить электронными деньгами за хороший алгоритм

отправьте мои деньги за алгоритм детям Уганды - http://iccf-holland.org/donate.html

[yurican]

Спасибо, ринулся изучать! )

[yurican]

не пойму как это отличается от вашей основной проблемы, но впрочем неважно

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

[mserg]

Самое естественное для таких задач – это линейное программирование (для несложных задач типа этой можно использовать Excel).

Заводим псевдобулевы переменные x(i,j) (в математическом смысле), каждая из которых принимает 1 только в том случае, если товар j будет куплен у поставщика i. Также заводится псевдобулева переменная y(i) поставщика. Далее составляются ограничения
* Покупаем каждый товар только у одного продавца
* Продавец является поставщиком (это y(i)=1) только в том случае, если он будет поставлять хотя бы один товар
* Количество поставщиков = указанное количество
Критерий – минимальная стоимость заказа

На современных компьютерах эта задача в Excel решится за миллисекунды.

При определенном навыке, для таких задач от момента прочтения до получения решения нужно несколько минут. Постановку задачи можно изменить, например, не фиксирую количество поставщиков, а введя в задачу шкалу стоимости затрат на количество поставщиков. Тогда можно получить реально оптимальное решение (с учетом своих затрат на возню с поставщиками).

это задача не линейного программирования, а линейного *целочисленного* программирования. ваш excel разве их решает?

На современных компьютерах эта задача в Excel решится за миллисекунды.

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

И каким образом в транспортной сети задаётся ограничение на количество продавцов? В конце концов, если максимальное число продавцов, с которым он всё ещё согласен иметь дело, не очень велико (порядка 3-4), можно просто перебрать все тройки-четвёрки продавцов, выбрав наилучший вариант.

И каким образом в транспортной сети задаётся ограничение на количество продавцов?

никак не задать. это будет np сложно, minimum set cover сводится к этому очевидно

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

[mserg]

Для тех кто в танке: в Excel есть численные методы, в том числе (частично-) целочисленное линейное программирование. Эта задача - не проблема.