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

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

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

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

Помогите решить задачу по переупаковке
Добрый день всем!
Задача на первый взгляд не сложная, но я затрудняюсь найти решение.
Суть в следующем.
Существует потребность в n Еденицах товара, который хранится в упаковках, количество которых произвольно ограничено, допустим
Уп.1 - 20Ед. - 5Шт.
Уп.2 - 30Ед. - 5Шт.
Уп.3 - 50Ед. - 3Шт.
Уп.4 - 100Ед. - 1Шт.
В решении требуется составить алгоритм, который будет:
1.Минимизировать свободный остаток товара после вскрытия упаковки(если нам нужно 75 едениц то вскрываем одну Уп.3 и одну Уп.2)
2.Во вторую очередь он должен минимизировать количество вскрываемых упаковок при минимальном остатке товара, то есть если нужно 145 едениц то вскрываем Уп.4 и Уп.3
Сложность состоит в том что количество упаковок может быть произвольным, как и количество едениц в них.
Спасибо, надеюсь на Вашу помощь!
  #2  
Старый 12.08.2010, 00:07
Пользователь

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

Задача решается с помощью линейного программирования (оно есть, например, в Excel).
Можно решить задачу в две фазы
1. Нахождение решения с минимальным остатком
2. Зная остаток из п.1, можно минимизировать количество коробок.
Для составления условий задач нужно «завести» в модели целочисленные переменные x(i), которые обозначают, сколько вскрывается коробок i-й типа. Ну, и далее, с помощью них составить ограничения и критерий. Дальше тело техники (линейного программирования) – система решения (тот же Excel) выдаст результат.

Может быть, задачу можно свести к задаче специального вида и решать его методом неявного перебора – но это уже садомазохизм.
  #3  
Старый 12.08.2010, 07:10
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

Если n не слишком велико, то можно решать динамическим программированием
 


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

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


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Помогите решить задачу. Loonar Графы 10 12.12.2010 15:42
Помогите решить задачу по VB 6.0 гость Реализация, исходники, языки 1 03.10.2009 23:56
Помогите решить задачу по C++ Andrei Сортировка и поиск 1 20.11.2008 18:06
Помогите решить задачу Misha1 Математические алгоритмы (другое) 2 10.09.2007 01:44
помогите решить задачу Annet Оффтопик 0 16.12.2006 16:58