Гость
Войти | Профиль | Очистить
Целевая тема:
Создать новую тему:
Автор:
Действия ...
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Задача максимальной укладки упаковок? Как? / 14 сообщений из 14, страница 1 из 1
31.10.2006, 14:24
    #34094303
Bill Great
Bill Great
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задача максимальной укладки упаковок? Как?
Привет всем! Задача - пусть есть склад торгующий плиткой. Плитка на складе в разных упаковках, скажем по 3 штуки упаковке, 17 штук в упаковке и т.д.Упаковки разрывать нельзя. Нужен алгоритм подбирающий упаковки для покупателя которому нeжно N плиток так что бы нехватка была минимальна! Скажем есть только упаковки по 17 шт. то заказ в 5 штук отоварить нельзя, а в 20 штук только 1 упакокой с "остатком" 3. За любую иформацию про алгоритм большое спасибо!
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
31.10.2006, 14:53
    #34094458
michael R
michael R
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задача максимальной укладки упаковок? Как?
посмотри
СИМПЛЕКС-МЕТОД
может поможет
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
31.10.2006, 15:19
    #34094590
michael R
michael R
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задача максимальной укладки упаковок? Как?
http://www.brsu.brest.by/pages/centr_pmo/au2.html
уравнения Диофанта

с симплексом поторопился
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
31.10.2006, 16:55
    #34095099
michael R
michael R
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задача максимальной укладки упаковок? Как?
что выбрать если остаток одинаковый

что предпочтительней кол-во коробок
или кол-во плиток в коробке при выборе
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
01.11.2006, 15:16
    #34097886
Valer
Valer
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задача максимальной укладки упаковок? Как?
вашу задачу можно рассматривать как
задачу о рюкзаке
есть предметы - упаковки ( размер n1 n2 n3 )
из них надо набрать то что нужно вашему клиенту
дома где то валяется решение
если найду вышлю на mik2375@yandex.ru
алгоритм если не делать его рекурсивным
рассказывать долго
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
01.11.2006, 15:34
    #34097964
michael R
michael R
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задача максимальной укладки упаковок? Как?
задача о рюкзаке это просто у него сложнее
потому что нужно учитывать кол-во коробок по каждому типу коробки
и проверка наличия допустимого кол-ва на складе
тут действительно рекурсия
но пока не знаю как
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
01.11.2006, 17:00
    #34098388
Den_di
Den_di
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задача максимальной укладки упаковок? Как?
А какие проблемы? Можно и тупо решить: сначала вычисляем весь набор возможных значений (суммируем кол-во плиток в коробках, но в разумных пределах, например до миллиона (это как мне подсказали 1 в степени 7)). Получаем набор,сортируем. Ищем наибольшее непревосходящее значение ну или наименьшее превосходящее, так как всегда нужен запас
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
01.11.2006, 17:09
    #34098436
michael R
michael R
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задача максимальной укладки упаковок? Как?
что значит тупо считаем
любой счёт тупым быть не может

например

есть коробки по
3 4 5

нужно 16 плиток

можно получить так
5*3 + 3 остаток 2
4*4 остаток 0 оптимум
5*3 + 3 остаток 2

а если кол-во коробок по типам ограничено
то кол-во слагаемых в сумме может быть больше

кол-во коробок
по 3 -2
по 4 -2
по 5 -2

нужно 16 плиток
2*3 + 2*4 +1*5 остаток 3
1*3 + 2*4 +1*5 остаток 0 оптимум
2*5 + 2*3 остаток 0 оптимум
...............
итак далее

если кол-во типов коробок больше то возможностей больше
и как выбирать оптимум
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
01.11.2006, 17:22
    #34098517
S.G.
S.G.
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задача максимальной укладки упаковок? Как?
michael R
и как выбирать оптимумспросить заказчика, так ли ему важен самый оптимальный оптимум, или можно и хоть как, но чтобы быстрее сделать ;)

но что- то мне говорит, что вариантов тут много быть не может, так что перебрать все что можно, времени не отнимет. если 2 и более вариантов будут одинаковы, выбрать любой.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
01.11.2006, 17:26
    #34098532
michael R
michael R
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задача максимальной укладки упаковок? Как?
ну а если ввести понятие цена на коробку
оптимум это
минимальная цена + минимальный остаток + минимум всех купленных коробок
хотя всё-равно не понятно какая стратегия и какой алгоритм
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
01.11.2006, 17:38
    #34098593
Den_di
Den_di
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задача максимальной укладки упаковок? Как?
Ладно. Тогда так: можно ли просчитать все возможные варианты: Их всегда в реальности не так много (ну не будет никто брать больше миллиона плиток). Можно их отсортировать - можно. Можно в них найти - можно. Или эта чиста экспериментальная задача для мыссленного решения без практического применения. Притом какой из оптимумов нужен?
Простой пример: есть коробки по 3 и 5 плиток:
Имеем набор: 3 5 6 8 9 10 11 12 13 14 15 ... ну и далее есть все числа:
Для каждого набора сохраняем, как мы его получили. Далее сортируем, ищем, получаем набор оптимальных решений, берём требуемое. Или опять что-то не так. Если вы о оптимальном быстром решении, то тут надо добирать по максимуму, если перебрали, то отнимать, снова добирать и так рекурсия.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
01.11.2006, 17:51
    #34098645
softwarer
softwarer
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задача максимальной укладки упаковок? Как?
Bill GreatЗа любую иформацию про алгоритм большое спасибо!
Насколько я помню определения, это таки bounded knapsack problem, в теории решается методом динамического программирования (гугль в помощь).

Для склада, торгующего плиткой, я бы предложил заранее рассчитать оптимальные конфигурации для значений меньше k*N (N - размер самой большой пачки, k - коэффициент, подобранный по вкусу), и запускать расчет по месту только при нехватке товара для выполнения стандартной разбивки.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
01.11.2006, 17:54
    #34098655
michael R
michael R
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задача максимальной укладки упаковок? Как?
softwarer
а можно по подробнее о динамическом программировании

это не моя задача как вы видите в топиках
но мне интересно
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
02.11.2006, 11:30
    #34100099
softwarer
softwarer
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задача максимальной укладки упаковок? Как?
michael Rа можно по подробнее о динамическом программировании
Легко
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Задача максимальной укладки упаковок? Как? / 14 сообщений из 14, страница 1 из 1
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]