Во вложении два алгоритма: Первый подбирает предметы суммарным весом не более необходимого, имеющие максимальную стоимость. Второй подбирает перечень предметов суммарным весом и стоимостью в определенном диапазоне от минимального до максимального.
В основе решения динамическое программирование, отсюда ограничения - работа с целыми числами, и существенное увеличение времени решения и количество выделяемой памяти от размеров рюкзака.
UPD 13/08/2015 Добавил решение классической "задачи о рюкзаке" жадным алгоритмом Не всегда находит наилучшее решение, но работает достаточно быстро
Во вложении два алгоритма: Первый подбирает предметы суммарным весом не более необходимого, имеющие максимальную стоимость. Второй подбирает перечень предметов суммарным весом и стоимостью в определенном диапазоне от минимального до максимального.
В основе решения динамическое программирование, отсюда ограничения - работа с целыми числами, и существенное увеличение времени решения и количество выделяемой памяти от размеров рюкзака.
UPD 13/08/2015 Добавил решение классической "задачи о рюкзаке" жадным алгоритмом Не всегда находит наилучшее решение, но работает достаточно быстроMCH
Что подразумевается под полным перебором? Нужно перебрать все 2^n комбинаций сочетания грузов и выбрать наилучший вариант? Учтите, что при количестве грузов более 20-25 данный способ не применим.
Чем плох вариант с динамическим программированием? ограничения на количество грузов практически нет.
Что подразумевается под полным перебором? Нужно перебрать все 2^n комбинаций сочетания грузов и выбрать наилучший вариант? Учтите, что при количестве грузов более 20-25 данный способ не применим.
Чем плох вариант с динамическим программированием? ограничения на количество грузов практически нет.MCH
Исходные условия: Есть прямоугольный контейнер размером X*Y Есть множество прямоугольных заполнителей размером X1*Y1 ... Xn*Yn Нужно уложить заполнители в контейнер максимально его заполнив по площади (с наименьшими пустотами) Количество каждого вида заполнителя неограниченно Заполнители можно вращать (на 90 градусов)
Вариант использования: уложить на паллет размерностью 1200*800 различные коробки с максимальной эффективностью (до задачи двумерного раскроя еще не дошел)
Выкладываю пример двумерной задачи о рюкзаке.
Исходные условия: Есть прямоугольный контейнер размером X*Y Есть множество прямоугольных заполнителей размером X1*Y1 ... Xn*Yn Нужно уложить заполнители в контейнер максимально его заполнив по площади (с наименьшими пустотами) Количество каждого вида заполнителя неограниченно Заполнители можно вращать (на 90 градусов)
Вариант использования: уложить на паллет размерностью 1200*800 различные коробки с максимальной эффективностью (до задачи двумерного раскроя еще не дошел)MCH
Добрый день. Не могли бы Вы помочь с решением нашей задачи. По большому счету задача очень схожа с Вашим файлом, за исключением того, что в нашем случае нельзя вращать Заполнители на 90 градусов. И не хватает итоговой суммы необходимых контейнеров для укладки всех заполнителей. russtalpg@yandex.ru
Добрый день. Не могли бы Вы помочь с решением нашей задачи. По большому счету задача очень схожа с Вашим файлом, за исключением того, что в нашем случае нельзя вращать Заполнители на 90 градусов. И не хватает итоговой суммы необходимых контейнеров для укладки всех заполнителей. russtalpg@yandex.ruРуссталь
Есть в планах на ближайшее будущее приступить к написанию алгоритма двумерного раскроя?
Задача двумерного раскроя достаточно сложна, у меня нет эффективного алгоритма для ее решения По Вашей задаче приложите фактические исходные данные (перечень деталей, размеры, количества) Лучше это сделать в отдельной теме форума, а не в "Готовых решениях"
Есть в планах на ближайшее будущее приступить к написанию алгоритма двумерного раскроя?
Задача двумерного раскроя достаточно сложна, у меня нет эффективного алгоритма для ее решения По Вашей задаче приложите фактические исходные данные (перечень деталей, размеры, количества) Лучше это сделать в отдельной теме форума, а не в "Готовых решениях"MCH
На базе задачи из сообщения № 7 Реализовал еще один алгоритм по двумерному рюкзаку (двумерной упаковке), который построен на переборе вариантов Медленный (переборный) алгоритм способен найти идеальное размещение (гильотинным раскроем), но очень сильно падает в скорости при увеличении размерности рюкзака
На базе задачи из сообщения № 7 Реализовал еще один алгоритм по двумерному рюкзаку (двумерной упаковке), который построен на переборе вариантов Медленный (переборный) алгоритм способен найти идеальное размещение (гильотинным раскроем), но очень сильно падает в скорости при увеличении размерности рюкзакаMCH
MCH, подскажите, пожалуйста, можно ли модернизировать макрос таким образом, чтобы в качестве исходных данных были: размерность контейнера, ширина и высота деталей и их количество? Т.е. задача отличается тем, что кол-во заполнителя у нас известно и его нужно оптимально разложить.
MCH, подскажите, пожалуйста, можно ли модернизировать макрос таким образом, чтобы в качестве исходных данных были: размерность контейнера, ширина и высота деталей и их количество? Т.е. задача отличается тем, что кол-во заполнителя у нас известно и его нужно оптимально разложить.ellison_shiny
Вход
Регистрация
Напомнить пароль
Автосумма
Часто используемые
ВПР
ЕСЛИ
СУММЕСЛИ
Финансовые
Логические
Текстовые
Даты и времени 
Ссылки и массивы 
Математические
Другие функции
Проверка свойств и значений
Баз данных
Математические
Обработки массивов
Обработки строк
Преобразования типов данных 
Загрузки данных
Работы с файлами
Обработки системных параметров
Обработки цвета
Работы с датами и временем
Преобразования в системы счисления
Финансовые
