double arrow

Решение задачи о рюкзаке. Применение динамического программирования при решении оптимизационных задач обычно предполагает создание специальных таблиц для хранения промежуточных

1

Применение динамического программирования при решении оптимизационных задач обычно предполагает создание специальных таблиц для хранения промежуточных результатов.

На рис. 2 изображены таблицы, которые используются для решения задачи о рюкзаке методом динамического программирования. Векторы, определяющие размеры () и стоимости () типов предметов, а также величина, характеризующая вместимость рюкзака (), заданы в верхней части рисунка.

Рис. 2. Таблицы, используемые для хранения промежуточных результатов, при решении задачи о рюкзаке методом динамического программирования

Количество таблиц, которое необходимо построить для решения поставленной задачи, соответствует заданному в задаче – количеству типов предметов (на рис. 2 ). Каждая таблица, кроме помеченной символом S, пронумерована и описывает все возможные случаи размещения в рюкзаке соответствующего типа предметов.

Например, таблица Т.0 описывает все возможные способы размещения в рюкзаке предметов, имеющих объем 85 и стоимость 150 за единицу веса, а таблица T.1 – все способы размещения предметов объемом 50 и стоимостью 25.

Все таблицы имеют одинаковую структуру и содержат по три столбца: неиспользованный объем места в рюкзаке, объем, занятый соответствующим типом, стоимость вещей в рюкзаке.

Например, первая строка таблицы T.0 соответствует случаю, когда в рюкзак не помещено ни одного предмета этого типа. Третья строка описывает случай, когда в пустой рюкзак помещено два предмета, которые заняли объем Третий столбец третей стоки содержит стоимость двух предметов, равную = единиц.

Десятая строка таблицы T.1 соответствует случаю, когда в рюкзаке остался незанятый объем, равный 215, и туда поместили два предмета, имеющих объем по 50 единиц. При этом общая стоимость вещей в рюкзаке вычисляется как сумма стоимости предметов, размещенных ранее (таблица T.0) в объеме и предметов, помещенных в данный момент.

Определить стоимость ранее размещенных предметов можно по таблице T.0. Для этого необходимо найти строку, которая соответствует остатку 215. Это вторая строка, так как она описывает размещение в пустом рюкзаке (300 единиц незанятого объема) одного предмета объемом 85 и стоимостью 12 750. Таким образом, стоимость предметов в рюкзаке, которая будет записана в десятой строке таблицы T.1, будет

Построение таблиц осуществляется последовательно в порядке их нумерации. Каждая таблица строится на основе предшествующей. Таблица, помеченная символом S, имеет чисто техническое назначение и предназначена для построения таблицы T.0. Таблица S состоит из одной строки, в первом столбце этой строки указывается вместимость рюкзака, а два другие столбца заполняются нулями.

Таблица с номером (далее просто таблица k) строится на основе таблицы При этом будем считать, что таблица S имеет номер –1 (минус один).

Каждой строке в таблице соответствует строк в таблице где – содержимое первого, – второго, – третьего столбца таблицы а – объем предмета k -го типа. Строки таблицы соответствующие строке таблицы имеют следующий вид: где – стоимость единицы объема предмета k -го типа.

В последней таблице (в нашем случае в таблице T.6) каждая строка соответствует одной из допустимых комбинаций предметов, помещенных в рюкзак. Для выбора комбинации, имеющей наибольшую стоимость, необходимо просмотреть всю таблицу и выбрать строку, в которой третий столбец имеет максимальное содержимое (на рис. 7.22 эта строка выделена, содержимое третьего столбца – 39 650). Далее следует восстановить путь построения этой строки, продвигаясь от последней таблицы к первой, используя значение третьего столбца в качестве ключа.

Для того чтобы определить строку в таблице T.5, необходимо вычислить значение ее третьего столбца. Оно равно разнице содержимого третьего столбца выделенной в таблице T.6 строки (39 650) и стоимости предметов, общий объем которых является значением второго столбца (это значение равно 0). Таким образом, разница состовлять Искомая в таблице T.5 будет иметь значение 37 650 в третьем столбце (на рис. 7.22 эта строка выделена).

Отыскав в таблице T.5 необходимую строку, следует подобным способом дойти до таблицы T.0 (на рис. 7.22 все выбранные строки выделены). Разделив содержимое выделенных строк на объем соответствующего таблице типа предмета, получим их количество. Таким образом, решением данной задачи будет вектор каждая компонента которого – количество предметов соответствующего типа.

На рис. 3 и 4 представлена функция knapsack_d, реализующая алгоритм динамического программирования решения задачи о рюкзаке.

Рис. 3. Прототип функции knapsack_d

Рис. 4. Реализация функции knapsack_d

Рис. 4. Окончание

Прототип функции knapsack_d ничем не отличается от прототипа функции knapsack_r,описанной ыше, поэтому не будем останавливаться на описании параметров.

Реализация функции knapsack_d претерпелазначительные изменения, обусловленные необходимостью сохранять промежуточные результаты вычислений. Для хранения промежуточных результатов применяется структура Table (структура моделирует таблицу в описанном выше алгоритме), представляющую собой коллекцию структур Element (строки таблицы). Конструктор структуры Table имеет единственный параметр, задающий количество элементов типа Element в коллекции.

Для работы со структурами Table и Element служат вспомогательные функции create и insert. Функция create создает (и возвращает) структуру Table на основе предшествующей структуры Table, заданной первым параметром. Второй и третий параметры задают размер и стоимость предмета, для которого строится таблица. Для вставки строк в созданную таблицу (структуру Table) используется функция insert.

Функция insert имеет пять параметров: t (таблица, в которую добавляются строки), V (остаток неиспользованного объема в рюкзаке), v (объем размещаемого предмета), C (стоимость предметов в занятом объеме рюкзака), с (стоимость размещаемого предмета).

Условно весь текст функции knapsack_d можно разбить на две части: сначала с помощью функции create создается массив таблиц (структур Table), а далее обратным ходом формируется решение.

Если в программе, приведенной на рис. 7 (см. пред. лекц.) заменить вызов функции knapsack_r на knapsack_d, проинициализировать переменную V, массивы v и c соответствующими значениями из условия задачи на рис. 2, а также правильно задать количество предметов (изменить макрос NN), то результат выполнения этой программы будет таким же, как на рис. 5.

Рис. 7.5. Результат решения задачи о рюкзаке


Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:  


1

Сейчас читают про: