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

Программа-калькулятор для решения задачи о рюкзаке 0-1 или 0-1 knapsack problem (достаточно большого размера) LargeKnapsack здесь А более полная версия статьи на ЗЕРКАЛЕ здесь

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

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


А это Задача о ранце (рюкзаке) на VBA Excel 2007...

Пример решений задачи на VBA Excel 2007
Рис.1        Пример решений задачи на VBA Excel 2007(и выше) поддерживает дробные числа

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

Условия получения кода?    Показать?


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



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


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

Пример решений задачи на C++, C# Visual Studio
Рис.2        Пример решений задачи на C++, C# Visual Studio 2008, 2012 (и выше)

Приложение обеспечивает возможность работы с файлами (сохранять и загружать наборы)...

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

Условия получения кода?    Показать?


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

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



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


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

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

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

Условия получения кода?    Показать?


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





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




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

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

Акция !!!
Весь код по 49 руб


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

Program code