Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 30.12.2010, 12:53
Новичок

Отправить личное сообщение для yurican Посмотреть профиль Найти все сообщения от yurican
 
Регистрация: 30.12.2010
Сообщений: 10

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

Есть двумерный массив
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 товара.
Найти самого выгодного продавца не является проблемой (можно просто просуммировать столбцы и получить ИТОГО).
Найти список продавцов, чтобы ИТОГО получилось наименьшим, также не проблема.

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

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

Последний раз редактировалось yurican, 30.12.2010 в 13:31.
  #2  
Старый 30.12.2010, 16:38
гocть

 
Сообщений: n/a

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

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

Цитата:
Готов заплатить электронными деньгами за хороший алгоритм
отправьте мои деньги за алгоритм детям Уганды - http://iccf-holland.org/donate.html
  #3  
Старый 30.12.2010, 17:03
Новичок

Отправить личное сообщение для yurican Посмотреть профиль Найти все сообщения от yurican
 
Регистрация: 30.12.2010
Сообщений: 10

Спасибо, ринулся изучать! )
  #4  
Старый 30.12.2010, 17:09
Новичок

Отправить личное сообщение для yurican Посмотреть профиль Найти все сообщения от yurican
 
Регистрация: 30.12.2010
Сообщений: 10

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

Отправить личное сообщение для mserg Посмотреть профиль Найти все сообщения от mserg
 
Регистрация: 29.10.2006
Сообщений: 57

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

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

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

При определенном навыке, для таких задач от момента прочтения до получения решения нужно несколько минут. Постановку задачи можно изменить, например, не фиксирую количество поставщиков, а введя в задачу шкалу стоимости затрат на количество поставщиков. Тогда можно получить реально оптимальное решение (с учетом своих затрат на возню с поставщиками).
  #6  
Старый 31.12.2010, 06:47
гocть

 
Сообщений: n/a

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

Цитата:
На современных компьютерах эта задача в Excel решится за миллисекунды.
5 поставщиков, 4 товара - да, совеременные методы решения общих задач целочисленного программирования решат. тысячи поставщиков, тысячи товаров - сомневаюсь. а вот поток - по сути, метод решения ЦЛП специального вида, решит.
  #7  
Старый 31.12.2010, 09:52
гость1

 
Сообщений: n/a

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

 
Сообщений: n/a

Сообщение от гость1 Посмотреть сообщение
И каким образом в транспортной сети задаётся ограничение на количество продавцов?
никак не задать. это будет np сложно, minimum set cover сводится к этому очевидно
  #9  
Старый 31.12.2010, 10:12
гocть

 
Сообщений: n/a

в общем, пусть автор топика выскажется столько продавцов, сколько товаров, и надо ли минизировать число продавцов.
  #10  
Старый 31.12.2010, 11:00
Пользователь

Отправить личное сообщение для mserg Посмотреть профиль Найти все сообщения от mserg
 
Регистрация: 29.10.2006
Сообщений: 57

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


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Равные суммы гость Задачи 4 18.03.2010 08:02
Алгоритм оптимальной нарезки Рафаэль Математические алгоритмы (другое) 5 02.07.2009 20:47
Задача построения оптимальной сетки гость Реализация, исходники, языки 0 25.11.2007 15:20
Задача построения оптимальной сетки EVerGreEN Задачи 0 25.11.2007 15:20
задача оптимальной раскройки Cross Задачи 4 09.01.2007 10:28