Применение генератора бинарных массивов к решению прикладных задач

, ФГБОУ ВПО ДВГГУ

, МБОУ «Математический лицей»

Применение генератора бинарных массивов к решению прикладных задач

Массивы – один из наиболее простых стандартных типов данных, используемых в большинстве языков программирования. Однако эта «простота» не мешает применять данный тип данных при решении достаточно сложных задач. Одну из таких задач – задачу об упаковке рюкзака – мы рассмотрим в данной статье.

Постановка задачи

У туриста имеется набор предметов, которые могут быть полезными в походе. Для каждого предмета определена (в баллах) его полезность. Кроме того, каждый предмет имеет некоторую массу. Грузоподъемность рюкзака ограничена некоторым числом, превысить которое нельзя. Требуется упаковать предметы в рюкзак так, чтобы их суммарная полезность была наибольшей, а суммарная масса не превысила максимальную грузоподъёмность.

Данная задача относится к, так называемым, трудно решаемым проблемам. Это означает, что точные алгоритмы ее решения являются «переборными» и имеют высокую трудоемкость.

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

Описание алгоритма

Решение задачи при любом конечном наборе предметов можно получить следующим образом:

- Первоначально за оптимальное текущее значение суммарной полезности берется ноль.

- Генерируются всевозможные комбинации предметов, вычисляется их суммарный вес и суммарная полезность.

- Если суммарный вес оказывается больше допустимого, то выполняется переход к следующей комбинации.

- Если суммарный вес оказывается в пределах допустимого, то тогда суммарная полезность сравнивается с текущей оптимальной. Если она не больше текущей оптимальной, то выполняется переход к следующей комбинации, если больше, тогда она становится текущей оптимальной, а текущая комбинация сохраняется как текущая оптимальная. После этого выполняется переход к следующей комбинации.

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

Как было сказано выше, этот алгоритм является переборным. Для его выполнения, в случае, когда дано N0 предметов, потребуется рассмотреть 2N0-1 комбинацию (для 20 предметов число комбинаций превысит миллион, а для 30 - миллиард). Тем не менее, современные компьютеры позволяют довольно быстро сгенерировать и проанализировать все возможные варианты даже при относительно большом количестве предметов. Поэтому перейдем к задаче генерирования всевозможных комбинаций из предметов.

Генетический код подмножества

Проясним используемую терминологию. Пусть имеется некоторое множество и пусть - его подмножество. Рассмотрим массив , состоящий из нулей и единиц. Если в этом массиве положить , а остальные элементы считать равными нулю, то мы получим генетический код подмножества B.

Таким образом, генетический код подмножества, это массив из нулей и единиц (массивы такого вида часто называют бинарными). Причем единицы расположены только на тех местах, которые соответствуют номерам элементов множества A, включенным в подмножество B.

Примеры

1. Пусть . Генетический код множества A состоит только из единиц (включены все элементы): .

2. Генетический код пустого множества состоит только из нулей (не выбран ни один из элементов): .

3. Множеству соответствует код .

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

Алгоритм порождения всех бинарных массивов заданной длины

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

Прибавление единицы в двоичной системе организовано так:

1. Ищется конец слова, являющегося двоичной записью числа.

2. От конца слова в начало пошагово рассматриваются символы: до тех пор, пока не встречен ноль, при этом все единицы заменяют на нули, а первый встреченный ноль заменяют на единицу и процесс останавливается.

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

Некоторую проблему в данном алгоритме представляет правило остановки: как определить, что все генетические коды уже рассмотрены?

В предложенном алгоритме остановка должна произойти, когда все элементы массива равны единице. Это можно обусловить по-разному: считать сумму элементов и сравнивать ее с числом N0, или считать произведение элементов и сравнивать его с единицей.

Мы используем другой прием: добавим к массиву еще один (N0+1) элемент. Обращение этого элемента в единицу как раз будет означать, что для предыдущих N0 элементов рассмотрены все возможные комбинации.

Ниже приводится листинг программы, генерирующей и выводящей на экран все варианты генетического кода – бинарные массивы заданной длины.

program int2bin;[1] {программа для генерирования всех возможных бинарных массивов длины N0}

const

N0 = 10; {количество элементов в массиве}

var

i, j, k: integer; {индексы}

b: array [1..N0 + 1] of integer; {массив бинарного кода}

begin

for i := 1 to N0 + 1 do {инициализация массива (заполнение нулями)}

b[i] := 0;

while b[N0 + 1] = 0 do {проверка условия, что сгенерированы не все коды}

begin

j := 1;

while b[j] > 0 do {поиск в текущем коде первого нулевого элемента

для прибавления единицы}

begin

b[j] := 0; {замена идущих подряд от начала единиц нулями}

j := j + 1;

end;

b[j] := 1; {завершение прибавления единицы - первый

встреченный 0 меняем на 1}

end;

writeln();

for k := 1 to N0 do {печать текущего генетического кода}

write(b[k],’ ‘);

end.

Реализация алгоритма оптимальной упаковки рюкзака

Теперь, когда нами создан генератор бинарных кодов, применим его к поиску оптимальной упаковки рюкзака. Ниже приведен листинг программы на языке Pascal.

program Knapsac; {программа упаковки рюкзака предметами данной

ценности и известной массы}

const

N0 = 8; {количество элементов в массиве}

Mmax = 32; {максимальный вес рюкзака}

var

i, j, k: integer; {индексы}

Mit, Zit, Mtek, Ztek: longint; {текущие значения массы и ценности выборки}

b, b0: array [1..N0 + 1] of integer; {текущие исследуемый и оптимальный

генетические коды}

zena, m: array [1..N0] of integer; {массивы, определяющие ценность и

вес предметов}

begin {начало программы}

for i := 1 to N0 + 1 do {инициализация бинарного массива

(заполнение нулями)}

b[i] := 0;

b0 := b;

{задание значений веса и ценности предметов}

zena[1] := 21;zena[2] := 2;zena[3] := 1;zena[4] := 11;zena[5] := 3;zena[6] := 5;zena[7] := 9;zena[8] := 23;

m[1] := 2; m[2] := 1; m[3] := 4; m[4] := 5; m[5] := 7; m[6] := 2; m[7] := 3; m[8] := 31;

Mtek := 0; Ztek := 0; {сброс счетчиков лучших текущего веса и

текущей ценности выборки предметов}

{НАЧАЛО ВЫЧИСЛЕНИЙ}

while b[N0 + 1] = 0 do {проверка условия, что сгенерированы не все коды}

begin

j := 1;

while b[j] > 0 do {поиск в текущем коде первого нулевого элемента

для прибавления единицы}

begin

b[j] := 0; {замена идущих подряд от начала единиц нулями}

j := j + 1;

end;

b[j] := 1; {завершение прибавления единицы – первый

встреченный 0 меняем на 1}

Mit := 0; Zit := 0;

for k := 1 to N0 do

begin

Mit := Mit + m[k] * b[k];

Zit := Zit + zena[k] * b[k];

end;

if (Mit < Mmax) and (Zit > Ztek) then

begin

Mtek := Mit;

Ztek := Zit;

b0 := b;

end;

end;

{Вывод на экран результатов поиска}

writeln('максимальная масса =', Mtek);

writeln('максимальная цена =', Ztek);

for i := 1 to N0 do

if b0[i] = 1 then

begin

writeln('предмет', i, '=', m[i], ' по цене ', zena[i]);

end;

end.

Задания для самостоятельного решения

Предлагаемые здесь задания являются контрольной работой №2 для учащихся 8-11 классов. Решите эти задания, запишите решения в отдельную (от физики и математике) тетрадь. Укажите на обложке следующую информацию о себе:

1. Фамилия, имя, класс, профиль класса (например: Сидоров Василий,10 кл., математический)

2. Индекс, адрес места жительства, электронная почта (если есть), телефон (домашний или мобильный)

3. Данные о школе (например: МБОУ №1 п. Бикин)

4. Фамилия, И. О. учителя информатики (например: учитель информатики )

Вы также можете прислать решения по электронной почте на адрес:

*****@***ru

Задание 1. Доработайте предложенную в статье программу упаковки рюкзака:

1.1. Преобразуйте часть кода программы, генерирующую бинарные массивы в процедуру или функцию и напишите новую программу, использующую эту процедуру.

1.2. Модернизируйте программу так, чтобы исходные данные считывались из файла inp.txt, а результаты сохранялись в файл out.txt. Форматы этих файлов можете установить самостоятельно, но обязательно в сопроводительной записке опишите эти форматы.

Задание 2. Напишите программу, решающую следующую версию проблемы упаковки рюкзака:

В рюкзак помещают два вида вещей – продукты и снаряжение. Максимальный вес рюкзака ограничен числом Mmax. Кроме этого, и для продуктов и для снаряжения установлены минимальные значения полезности Pv и Ps. Нужно упаковать рюкзак, обеспечив при этом максимальную полезность груза. Причем суммарная полезность выбранных продуктов и суммарная полезность выбранного снаряжения не должны быть меньше Pv и Ps соответственно.

Желаем удачи!

[1] В TurboPASCAL для корректного вывода данных на экран может потребоваться подключение модуля CRT, для этого после заголовка с новой строки введите текст: USES CRT;