Домашняя страница Undo Do New Save Карта сайта Обратная связь Поиск по форуму
МИР MS EXCEL - Гость.xls

Вход

Регистрация

Напомнить пароль

 

= Мир MS Excel/Задача о рюкзаке - Мир MS Excel

Старая форма входа
  • Страница 1 из 1
  • 1
Модератор форума: _Boroda_, китин  
Задача о рюкзаке
MCH Дата: Среда, 12.08.2015, 20:40 | Сообщение № 1
Группа: Админы
Ранг: Старожил
Сообщений: 2004
Репутация: 752 ±
Замечаний: ±

В продолжении темы "Подбор слагаемых под нужную сумму" (сумма подмножеств)
Предлагаю решение "Задачи о рюкзаке"

Во вложении два алгоритма:
Первый подбирает предметы суммарным весом не более необходимого, имеющие максимальную стоимость.
Второй подбирает перечень предметов суммарным весом и стоимостью в определенном диапазоне от минимального до максимального.

В основе решения динамическое программирование, отсюда ограничения - работа с целыми числами, и существенное увеличение времени решения и количество выделяемой памяти от размеров рюкзака.

UPD 13/08/2015
Добавил решение классической "задачи о рюкзаке" жадным алгоритмом
Не всегда находит наилучшее решение, но работает достаточно быстро
К сообщению приложен файл: Rucksack.xlsm (73.9 Kb)
 
Ответить
СообщениеВ продолжении темы "Подбор слагаемых под нужную сумму" (сумма подмножеств)
Предлагаю решение "Задачи о рюкзаке"

Во вложении два алгоритма:
Первый подбирает предметы суммарным весом не более необходимого, имеющие максимальную стоимость.
Второй подбирает перечень предметов суммарным весом и стоимостью в определенном диапазоне от минимального до максимального.

В основе решения динамическое программирование, отсюда ограничения - работа с целыми числами, и существенное увеличение времени решения и количество выделяемой памяти от размеров рюкзака.

UPD 13/08/2015
Добавил решение классической "задачи о рюкзаке" жадным алгоритмом
Не всегда находит наилучшее решение, но работает достаточно быстро

Автор - MCH
Дата добавления - 12.08.2015 в 20:40
nerv Дата: Суббота, 15.08.2015, 14:44 | Сообщение № 2
Группа: Редакторы
Ранг: Обитатель
Сообщений: 431
Репутация: 193 ±
Замечаний: 0% ±

К сожалению, не могу запустить в Libre Office макросы VBA.

Добавил решение классической "задачи о рюкзаке" жадным алгоритмом
Не всегда находит наилучшее решение, но работает достаточно быстро

В качестве дополнения можно попытаться решить данную задачу
1. Алгоритмом имитации отжига
2. Генетическим алгоритмом


Чебурашка стал символом олимпийских игр. А чего достиг ты?
Тишина - самый громкий звук


YM 41001156540584 / WM WMR R21924176233

https://github.com/nervgh/vba


Сообщение отредактировал nerv - Суббота, 15.08.2015, 14:44
 
Ответить
СообщениеК сожалению, не могу запустить в Libre Office макросы VBA.

Добавил решение классической "задачи о рюкзаке" жадным алгоритмом
Не всегда находит наилучшее решение, но работает достаточно быстро

В качестве дополнения можно попытаться решить данную задачу
1. Алгоритмом имитации отжига
2. Генетическим алгоритмом

Автор - nerv
Дата добавления - 15.08.2015 в 14:44
RAN Дата: Суббота, 15.08.2015, 16:07 | Сообщение № 3
Группа: Друзья
Ранг: Экселист
Сообщений: 5660
Репутация: 1163 ±
Замечаний: 0% ±

2010
Википедия больше не работает

[p.s.]Может и не поэтому, но все равно не работает![/p.s.]


Быть или не быть, вот в чем загвоздка!

Сообщение отредактировал RAN - Суббота, 15.08.2015, 16:24
 
Ответить
СообщениеВикипедия больше не работает

[p.s.]Может и не поэтому, но все равно не работает![/p.s.]

Автор - RAN
Дата добавления - 15.08.2015 в 16:07
Lina40 Дата: Понедельник, 18.01.2016, 22:58 | Сообщение № 4
Группа: Пользователи
Ранг: Прохожий
Сообщений: 5
Репутация: 0 ±
Замечаний: 0% ±

Excel 2010
Подскажите, пожалуйста, а есть где-нибудь решение задачи о рюкзаке методом полного перебора на vba.
 
Ответить
СообщениеПодскажите, пожалуйста, а есть где-нибудь решение задачи о рюкзаке методом полного перебора на vba.

Автор - Lina40
Дата добавления - 18.01.2016 в 22:58
MCH Дата: Вторник, 19.01.2016, 04:16 | Сообщение № 5
Группа: Админы
Ранг: Старожил
Сообщений: 2004
Репутация: 752 ±
Замечаний: ±

Что подразумевается под полным перебором?
Нужно перебрать все 2^n комбинаций сочетания грузов и выбрать наилучший вариант?
Учтите, что при количестве грузов более 20-25 данный способ не применим.

Чем плох вариант с динамическим программированием? ограничения на количество грузов практически нет.
 
Ответить
СообщениеЧто подразумевается под полным перебором?
Нужно перебрать все 2^n комбинаций сочетания грузов и выбрать наилучший вариант?
Учтите, что при количестве грузов более 20-25 данный способ не применим.

Чем плох вариант с динамическим программированием? ограничения на количество грузов практически нет.

Автор - MCH
Дата добавления - 19.01.2016 в 04:16
Lina40 Дата: Вторник, 19.01.2016, 09:59 | Сообщение № 6
Группа: Пользователи
Ранг: Прохожий
Сообщений: 5
Репутация: 0 ±
Замечаний: 0% ±

Excel 2010
Да, полный перебор всех комбинаций.
Методы решения задачи о рюкзаке

Он хорош, просто мне в работе необходимо использовать несколько методов :(
 
Ответить
СообщениеДа, полный перебор всех комбинаций.
Методы решения задачи о рюкзаке

Он хорош, просто мне в работе необходимо использовать несколько методов :(

Автор - Lina40
Дата добавления - 19.01.2016 в 09:59
MCH Дата: Вторник, 03.08.2021, 15:02 | Сообщение № 7
Группа: Админы
Ранг: Старожил
Сообщений: 2004
Репутация: 752 ±
Замечаний: ±

Выкладываю пример двумерной задачи о рюкзаке.

Исходные условия:
Есть прямоугольный контейнер размером X*Y
Есть множество прямоугольных заполнителей размером X1*Y1 ... Xn*Yn
Нужно уложить заполнители в контейнер максимально его заполнив по площади (с наименьшими пустотами)
Количество каждого вида заполнителя неограниченно
Заполнители можно вращать (на 90 градусов)

Вариант использования: уложить на паллет размерностью 1200*800 различные коробки с максимальной эффективностью
(до задачи двумерного раскроя еще не дошел)
К сообщению приложен файл: _2D.xlsm (62.4 Kb)
 
Ответить
СообщениеВыкладываю пример двумерной задачи о рюкзаке.

Исходные условия:
Есть прямоугольный контейнер размером X*Y
Есть множество прямоугольных заполнителей размером X1*Y1 ... Xn*Yn
Нужно уложить заполнители в контейнер максимально его заполнив по площади (с наименьшими пустотами)
Количество каждого вида заполнителя неограниченно
Заполнители можно вращать (на 90 градусов)

Вариант использования: уложить на паллет размерностью 1200*800 различные коробки с максимальной эффективностью
(до задачи двумерного раскроя еще не дошел)

Автор - MCH
Дата добавления - 03.08.2021 в 15:02
Руссталь Дата: Воскресенье, 15.08.2021, 17:07 | Сообщение № 8
Группа: Пользователи
Ранг: Прохожий
Сообщений: 5
Репутация: 0 ±
Замечаний: 20% ±

Добрый день.
Не могли бы Вы помочь с решением нашей задачи.
По большому счету задача очень схожа с Вашим файлом, за исключением того, что в нашем случае нельзя вращать Заполнители на 90 градусов. И не хватает итоговой суммы необходимых контейнеров для укладки всех заполнителей.
russtalpg@yandex.ru
К сообщению приложен файл: 2149044.docx (65.7 Kb)


Сообщение отредактировал Serge_007 - Понедельник, 16.08.2021, 15:07
 
Ответить
СообщениеДобрый день.
Не могли бы Вы помочь с решением нашей задачи.
По большому счету задача очень схожа с Вашим файлом, за исключением того, что в нашем случае нельзя вращать Заполнители на 90 градусов. И не хватает итоговой суммы необходимых контейнеров для укладки всех заполнителей.
russtalpg@yandex.ru

Автор - Руссталь
Дата добавления - 15.08.2021 в 17:07
Руссталь Дата: Понедельник, 23.08.2021, 14:14 | Сообщение № 9
Группа: Пользователи
Ранг: Прохожий
Сообщений: 5
Репутация: 0 ±
Замечаний: 20% ±

до задачи двумерного раскроя еще не дошел

Добрый день.
Есть в планах на ближайшее будущее приступить к написанию алгоритма двумерного раскроя?
 
Ответить
Сообщение
до задачи двумерного раскроя еще не дошел

Добрый день.
Есть в планах на ближайшее будущее приступить к написанию алгоритма двумерного раскроя?

Автор - Руссталь
Дата добавления - 23.08.2021 в 14:14
MCH Дата: Понедельник, 23.08.2021, 15:06 | Сообщение № 10
Группа: Админы
Ранг: Старожил
Сообщений: 2004
Репутация: 752 ±
Замечаний: ±

Цитата Руссталь, 23.08.2021 в 14:14, в сообщении № 9 ()
Есть в планах на ближайшее будущее приступить к написанию алгоритма двумерного раскроя?

Задача двумерного раскроя достаточно сложна, у меня нет эффективного алгоритма для ее решения
По Вашей задаче приложите фактические исходные данные (перечень деталей, размеры, количества)
Лучше это сделать в отдельной теме форума, а не в "Готовых решениях"
 
Ответить
Сообщение
Цитата Руссталь, 23.08.2021 в 14:14, в сообщении № 9 ()
Есть в планах на ближайшее будущее приступить к написанию алгоритма двумерного раскроя?

Задача двумерного раскроя достаточно сложна, у меня нет эффективного алгоритма для ее решения
По Вашей задаче приложите фактические исходные данные (перечень деталей, размеры, количества)
Лучше это сделать в отдельной теме форума, а не в "Готовых решениях"

Автор - MCH
Дата добавления - 23.08.2021 в 15:06
MCH Дата: Четверг, 05.05.2022, 17:44 | Сообщение № 11
Группа: Админы
Ранг: Старожил
Сообщений: 2004
Репутация: 752 ±
Замечаний: ±

На базе задачи из сообщения № 7
Реализовал еще один алгоритм по двумерному рюкзаку (двумерной упаковке), который построен на переборе вариантов
Медленный (переборный) алгоритм способен найти идеальное размещение (гильотинным раскроем), но очень сильно падает в скорости при увеличении размерности рюкзака
К сообщению приложен файл: 2D_Dynamic.xlsm (132.2 Kb)
 
Ответить
СообщениеНа базе задачи из сообщения № 7
Реализовал еще один алгоритм по двумерному рюкзаку (двумерной упаковке), который построен на переборе вариантов
Медленный (переборный) алгоритм способен найти идеальное размещение (гильотинным раскроем), но очень сильно падает в скорости при увеличении размерности рюкзака

Автор - MCH
Дата добавления - 05.05.2022 в 17:44
ellison_shiny Дата: Понедельник, 28.10.2024, 09:04 | Сообщение № 12
Группа: Пользователи
Ранг: Прохожий
Сообщений: 1
Репутация: 0 ±
Замечаний: 0% ±

MCH, подскажите, пожалуйста, можно ли модернизировать макрос таким образом, чтобы в качестве исходных данных были: размерность контейнера, ширина и высота деталей и их количество? Т.е. задача отличается тем, что кол-во заполнителя у нас известно и его нужно оптимально разложить.
 
Ответить
СообщениеMCH, подскажите, пожалуйста, можно ли модернизировать макрос таким образом, чтобы в качестве исходных данных были: размерность контейнера, ширина и высота деталей и их количество? Т.е. задача отличается тем, что кол-во заполнителя у нас известно и его нужно оптимально разложить.

Автор - ellison_shiny
Дата добавления - 28.10.2024 в 09:04
  • Страница 1 из 1
  • 1
Поиск:

Яндекс.Метрика Яндекс цитирования
© 2010-2024 · Дизайн: MichaelCH · Хостинг от uCoz · При использовании материалов сайта, ссылка на www.excelworld.ru обязательна!