Задача о ранце (рюкзаке) на VBA (EXCEL), C++, C# (Visual Studio) и Delphi
Программа-калькулятор для решения задачи о рюкзаке 0-1 или 0-1 knapsack problem (достаточно большого размера) LargeKnapsack здесь
Калькулятор-Упаковщик «Packer1» тоже использует алгоритм "задачи рюкзака" Программа-калькулятор расчета укладки продукции в упаковки
- Динамическое программирование. Что меня поразило в этом алгоритме
- Пример решений задачи на VBA Excel
- Пример решений задачи на C# Visual Studio
- Пример решений задачи на C++ Visual Studio
- Пример решений задачи на Delphi 7, XE
Условие 0-1 knapsack problem:
Из множества предметов со свойствами «стоимость» и «вес», отобрать некоторое их число таким образом,
чтобы получить максимальную суммарную стоимость при одновременном соблюдении ограничения на суммарный вес.
Динамическое программирование. Что меня поразило в этом алгоритме
Ведь задан вес - Р.
Кажется, кратчайшее решение - это рассматривать наборы только этого веса.
Число сочетаний С из n по m возрастает с увеличением m [от 1 до n/2], а затем будет убывать.
Так зачем рассматривать промежуточные наборы и тратить время.
Отсортировать предметы по убыванию «стоимости» и перебирать в цикле, проверяя условие: вес <=P.
Машина посчитает
Можно, даже, отсортировать по параметру удельной стоимости каждого предмета (стоимость/вес предмета), тогда каждый выше расположенный в ряду предмет будет предпочтительней, чем нижние.
А оказывается, нет. Рассматривая варианты для весов от 1 до Р (внутренний цикл > ячейки одной строки) и увеличивая количество предметов от 1 до n (внешний цикл > увеличение номера строки) становится возможной автоматическая оптимизация.
Делая выбор для очередной ячейки, выбирается максимум из двух вариантов:
Первый вариант: ячейка в этой же колонке, но на строку выше (т.е. просто, не брать этот предмет в ранец,
т.к. предыдущий набор предметов для данного веса «ценнее»).
Второй вариант: стоимость предмета + ячейка, которая на строку выше и левее на величину веса предмета
(т.е. берем предмет, но выбрасываем из ранца другие предметы на величину его веса).
Гениально...
А как красиво заполняется таблица Иногда, оказывается, следует выбрасывать предметы с большей удельной стоимостью, чтобы достичь максимальной загрузки ранца и от этого получить максимум стоимости в результат.
И даже сортировка излишня. Без нее результат абсолютно тот же. Предмет с большим удельным весом всегда будет размещаться алгоритмом (в строке таблицы) левее, чем остальные.
Экспериментируйте. Все наглядно.
В желтых ячейках можно задать параметры.
Кнопки Random, Sort, Massiv запускают определенные макросы.
Задача о ранце (рюкзаке) скачать xls-файл VBA Excel 2003
Пример решений задачи на VBA Excel 2007 и выше
А это Задача о ранце (рюкзаке) на VBA Excel 2010...
Рис.1 Пример решений задачи на VBA Excel
Скачать xlsm-файл для тестирования
Другие примеры на языке «Visual Basic for application - VBA»
Пример решений задачи на C# Visual Studio
Так может выглядеть главная форма...
Рис.2 Пример решений задачи на C# Visual Studio
скачать ехе-файл для тестирования
Пример решений задачи на C++ Visual Studio
Так может выглядеть главная форма...
Рис.3 Пример решений задачи на C++ Visual Studio
Замена фото (файл the_foto.jpg) на форме AboutForm - вопрос на любителя… Можно форму «О разработчике» удалить, если не требуется.
скачать ехе-файл для тестирования
Другие примеры на языках «C»,«C++»
Пример решений задачи на Delphi 7, XE
Главная форма...
Рис.5 Пример решений задачи на Delphi 7, XE
скачать ехе-файл для тестирования
Другие примеры на языке «Delphi»
Другие примеры на тему «Упаковка, укладка продукции. Раскрой материала.»
Если у Вас остались вопросы, то задать их Вы можете, нажав на эту кнопочку ...
Поделиться в соц сетях: