Задача о ранце (рюкзаке) на VBA (EXCEL), C++, C# (Visual Studio 2012) и DELPHI

Программа-калькулятор для решения задачи о рюкзаке 0-1 или 0-1 knapsack problem (достаточно большого размера) LargeKnapsack здесь

Калькулятор-Упаковщик «Packer1» тоже использует алгоритм "задачи рюкзака" Программа-калькулятор расчета укладки продукции в упаковки

  1. Динамическое программирование. Что меня поразило в этом алгоритме
  2. Пример решений задачи на VBA Excel
  3. Пример решений задачи на C# Visual Studio 2012
  4. Пример решений задачи на C++ Visual Studio 2012
  5. Пример решений задачи на 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...

Пример решений задачи на VBA Excel
Рис.1        Пример решений задачи на VBA Excel

Скачать xlsm-файл для тестирования



Другие примеры на языке «Visual Basic for application - VBA»



Пример решений задачи на C# Visual Studio 2012

Так может выглядеть главная форма...

Пример решений задачи на C# Visual Studio 2012
Рис.2        Пример решений задачи на C# Visual Studio 2012

скачать ехе-файл для тестирования



Другие примеры на языке «C#»



Пример решений задачи на C++ Visual Studio 2012

Так может выглядеть главная форма...

Пример решений задачи на C++ Visual Studio 2012
Рис.3        Пример решений задачи на C++ Visual Studio 2012

Замена фото (файл the_foto.jpg) на форме AboutForm - вопрос на любителя… Можно форму «О разработчике» удалить, если не требуется.

скачать ехе-файл для тестирования



Другие примеры на языках «C»,«C++»



Пример решений задачи на Delphi 7, XE

Главная форма...

Пример решений задачи на Delphi 7, XE
Рис.5        Пример решений задачи на Delphi 7, XE

скачать ехе-файл для тестирования



Другие примеры на языке «Delphi»

Другие примеры на тему «Упаковка, укладка продукции. Раскрой материала.»



Если у Вас остались вопросы, то задать их Вы можете, нажав на эту кнопочку ...




Если на этой странице не нашлось того, что Вы так искали...

         Не расстраивайтесь, не все потеряно... Смело щелкайте...
исходный код на заказ. orenstudent.ru Автоматизация документов MS Office. orenstudent.ru исходный код на заказ. orenstudent.ru Помогите найти и устранить ошибку в исходном коде программы. orenstudent.ru Skype-консультирование по программированию
Скайп-консультации

Акция !!!
исходный код комментарии цена минимальная


Не попадайтесь на удочку мошенников-кидал...
Сайт помощи студентам по программированию и информатике

Program code