Задача о ранце (или про рюкзак).

Этот алгоритм я увидел в Википедии. И только переписал его с С++ на VBA.

Условие:
Из множества предметов со свойствами «стоимость» и «вес», отобрать некоторое их число таким образом, чтобы получить максимальную суммарную стоимость при одновременном соблюдении ограничения на суммарный вес.

Что меня поразило в этом алгоритме:

Ведь задан вес - Р.
Кажется, кратчайшее решение - это рассматривать наборы только этого веса.
Число сочетаний С из n по m возрастает с увеличением m [от 1 до n/2], а затем будет убывать.
Так зачем рассматривать промежуточные наборы и тратить время.
Отсортировать предметы по убыванию «стоимости» и перебирать в цикле, проверяя условие: вес <=P.
Машина посчитает…

Можно, даже, отсортировать по параметру удельной стоимости каждого предмета (стоимость/вес предмета), тогда каждый выше расположенный в ряду предмет будет предпочтительней, чем нижние.

А оказывается, нет. Рассматривая варианты для весов от 1 до Р (внутренний цикл –> ячейки одной строки) и увеличивая количество предметов от 1 до n (внешний цикл – > увеличение номера строки) становится возможной автоматическая оптимизация.

Делая выбор для очередной ячейки, выбирается максимум из двух вариантов:
Первый вариант: ячейка в этой же колонке, но на строку выше (т.е. просто, не брать этот предмет в ранец, т.к. предыдущий набор предметов для данного веса «ценнее»).
Второй вариант: стоимость предмета + ячейка, которая на строку выше и левее на величину веса предмета (т.е. берем предмет, но выбрасываем из ранца другие предметы на величину его веса).

Гениально...

А как красиво заполняется таблица… Иногда, оказывается, следует выбрасывать предметы с большей удельной стоимостью, чтобы достичь максимальной загрузки ранца и от этого получить максимум стоимости в результат.

И даже сортировка излишня. Без нее результат абсолютно тот же. Предмет с большим удельным весом всегда будет размещаться алгоритмом (в строке таблицы) левее, чем остальные.

Экспериментируйте. Все наглядно.
В желтых ячейках можно задать параметры.
Кнопки Random, Sort, Massiv – запускают определенные макросы.

Задача о ранце (рюкзаке) скачать xls-файл VBA Excel 2003


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

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

Задача о ранце (рюкзаке) скачать xlsm-файл (поддерживает дробные числа)


А это Задача о ранце (рюкзаке) на Visual Studio 2008 C++...

Задача о рюкзаке (ранце) Visual Studio 2008 C++

Задача о ранце (рюкзаке) скачать exe-файл


А это Задача о ранце (рюкзаке) на Делфи...

Задача о рюкзаке (ранце) DELPHI 7

Задача о ранце (рюкзаке) скачать Delphi_7 exe-файл


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


Есть очень похожий по интерфейсу (на C++) готовый проект
на Visual Studio 2008 C++ с использованием MFC.

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

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

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




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

         Не расстраивайтесь, не все потеряно... Смело щелкайте...

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


и СТУДЕНТЫ!
Кому не плевать
на деньги!
Сайт помощи студентам по программированию и информатике