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

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

 
 
Опции темы Поиск в этой теме Опции просмотра
  #11  
Старый 31.12.2010, 11:24
Новичок

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

Сообщение от гocть Посмотреть сообщение
в общем, пусть автор топика выскажется столько продавцов, сколько товаров, и надо ли минизировать число продавцов.
Всегда по-разному, НО:
обычно товаров от 3 до 10
продавцов от 5 до 3000

минимизировать число продавцов... нет, не надо. Надо иметь возможность задавать, со сколькими продавцами готов возиться.

Excel мне не подходит, так как мне нужно это реализовать на каком-нибудь серверном языке программирования (например, php)
  #12  
Старый 31.12.2010, 11:30
Новичок

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

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

Последний раз редактировалось yurican, 02.01.2011 в 10:30.
  #13  
Старый 31.12.2010, 11:40
гocть

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

Цитата:
минимизировать число продавцов... нет, не надо. Надо иметь возможность задавать, со сколькими продавцами готов возиться.
это практически эквиваленто минимизации. NP-сложно.

Сообщение от yurican Посмотреть сообщение
Всегда по-разному, НО:
обычно товаров от 3 до 10
продавцов от 5 до 3000
ну а что же вы раньше молчали??? такие детали решают все. утаивать их почти криминал

10 товаров максимум - значит тут возможно решение динамическим программированием со сложностью O(2^n m), где n=10 число товаров (маску хранить надо, что было куплено), m=5000 число продавцов. Для простоты, предполагаю тут, что каждый товар покупаем только у одного продавца. В этот алгоритм уже несложно будет добавить ограничение на число торгашей, сложность увеличится до O(2^n m k), k=число торгашей.
  #14  
Старый 31.12.2010, 11:47
гocть

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

Цитата:
Excel мне не подходит, так как мне нужно это реализовать на каком-нибудь серверном языке программирования (например, php)
php не рекомендую. пиши на c/c++, вызывая их из php либо как отдельную программу либо как библиотеку.

если решишь делать через ILP, то с нуля писать категорически не рекомендую, есть несколько свободных солверов, вызываются через шелл, бери:
http://www.gnu.org/software/glpk/
http://lpsolve.sourceforge.net/5.5/
  #15  
Старый 31.12.2010, 11:49
Пользователь

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

Как вариант – есть еще open source пакет частично-целочисленного программирования lp_solve, который компилируется под множество платформ. Возможно, его использование будет проще, чем программировать такую задачу на php. Разработчики клянутся, что lp_solve легко интегрируется с php.

Еще одно преимущество: условия задачи со временем могут поменяться с изменением требований бизнеса. Гораздо проще исправить математическую модель, чем код на php. Точнее говоря, при написании кода на php любые изменения в требованиях потребует полностью переписать программу.
  #16  
Старый 31.12.2010, 12:01
Новичок

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

Сообщение от гocть Посмотреть сообщение
эДля простоты, предполагаю тут, что каждый товар покупаем только у одного продавца.
так и есть, каждый товар покупается только у одного продавца. Более того, каждый товар -- в единственном экземпляре.
  #17  
Старый 31.12.2010, 12:04
Новичок

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

То есть, мы пришли к тому, что реализовать можно на c/c++ и подключить к php?

Кто-нибудь может взяться за реализацию этой штуковины на сях? Я в них ни в зуб ногой.. я только на php

Сколько это будет стоить?
  #18  
Старый 31.12.2010, 12:12
Пользователь

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

Нужно только откомпилировать уже готовый пакет lp_solve, программировать на C++ не требуется. Потом, на php работать с этим пакетом.
http://lpsolve.sourceforge.net/5.5/PHP.htm

Последний раз редактировалось mserg, 31.12.2010 в 12:24.
  #19  
Старый 31.12.2010, 12:24
гocть

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

Сообщение от mserg Посмотреть сообщение
Нужно только откомпилировать уже готовый пакет lp_solve, программировать на C++ не требуется. Потом, на php работать с этим пакетом.
зачем палить из пушки по воробьям? при 10 товарах динамическое программирование будет гораздо быстрее. и причем, в отличие от ILP солверов, этот алгоритм основан не на переборных эвристиках, а значит на каком нибудь хитром тесте не попадет в кому, а ответит за гарантированное время.

Цитата:
Сколько это будет стоить?
динамика про которую я говорил? на олимпиадах по программированию это нынче из разряда легких задач, я бы дал минут 30 максимум на решение. зарплата разраба - ну, допустим, 50000 в месяц в default city, полчаса значит выйдет в 50000/28/8/2=110 рублей.
  #20  
Старый 31.12.2010, 13:06
Пользователь

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

Флаг Вам в руки – автор темы заплатит Вам без проблем 110 руб.

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


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

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


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Равные суммы гость Задачи 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