Russian Qt Forum
Ноябрь 23, 2024, 05:16 *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

Войти
 
  Начало   Форум  WIKI (Вики)FAQ Помощь Поиск Войти Регистрация  

Страниц: [1]   Вниз
  Печать  
Автор Тема: Оптимальное заполнение контейнера  (Прочитано 6331 раз)
jurtal
Гость
« : Сентябрь 13, 2012, 09:15 »

Всем привет!
Есть такая простая задачка. Даны два контейнера размером 12 и 10. В них надо поместить объекты размерами 6,6,7 и 3. Подскажите какой алгоритм посмотреть для реализации подобного размещения...
Записан
Serr500
Гость
« Ответ #1 : Сентябрь 13, 2012, 09:26 »

ru.wikipedia.org/wiki/Задача_о_ранце
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #2 : Сентябрь 13, 2012, 14:14 »

Сначала дал ссылку на предыдущую попытку, но потом увидел что автор тот же  Улыбающийся

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

Пробуйте улучшить метод который обсуждали (http://www.prog.org.ru/index.php?topic=23004.msg162442#msg162442). Ага, не влазит (вижу Вы так подобрали числа). Какой контейнер оказался "худшим"? (т.е. наибольшее число раз в него пытались всунуть но не вышло). Изменить порядок контейнеров перенеся "самый плохой" в хвост и повторить.

Записан
jurtal
Гость
« Ответ #3 : Сентябрь 13, 2012, 15:55 »

Сделал так... Все размещается - но думаю в этом случае есть такие комбинации, которые не разместяться таким способом... А метод простого перебора должен по-любому работать, но я пока не могу создать множество всех вариантов разбиения для проверки... Igors, спасибо...
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #4 : Сентябрь 13, 2012, 16:23 »

Можно попробовать "алгоритм с развратом"

Edit: что-то я Вику испугался (тлетворное влияние знаний). Если нет никаких требований по оптимальности - задачка-то детская (аттач)
« Последнее редактирование: Сентябрь 13, 2012, 18:34 от Igors » Записан
jurtal
Гость
« Ответ #5 : Сентябрь 14, 2012, 10:30 »

Можно попробовать "алгоритм с развратом"

Edit: что-то я Вику испугался (тлетворное влияние знаний). Если нет никаких требований по оптимальности - задачка-то детская (аттач)

Круто - все работает вроде... Спасибо... Буду разбираться с алгоритмом с возвратом...
Записан
Страниц: [1]   Вверх
  Печать  
 
Перейти в:  


Страница сгенерирована за 0.123 секунд. Запросов: 22.