Задача о ранце (рюкзаке) на 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