Решение упрощенной задачи о рюкзаке с помощью генератора множества всех подмножеств

Задача о рюкзаке является одной из известных задач, решаемых методом перебора. Сформулируем упрощенную задачу о рюкзаке.

Существует различных предметов, характеризующихся объемом и стоимостью,. Необходимо выбрать несколько разных предметов таким способом, чтобы они поместились в рюкзаке объемом и при этом их суммарная стоимость была максимальной.

Математическая модель задачи может быть записана следующим образом:

где – неизвестные, которые требуется найти.

Решением задачи при такой постановке будет вектор. Каждый элемент вектора может принимать значение или 1. При этом если то -ый предмет не выбран, и если то -й предмет выбран для размещения в рюкзаке.

13:

Задача имеет следующие исходные данные:

– вместимость (объем) рюкзака;

– количество предметов;

– вектор объемов предметов;

– вектор стоимостей предметов.

Рис. 6. Схема решения задачи о рюкзаке с применением генератора множества всех подмножеств

С помощью генератора всех подмножеств последовательно генерируются все массивы индексов (на рис. 6 второй слева столбец), соответствующие битовой последовательности (первый столбец слева). На основе массивов индексов формируются все возможные подмножества предметов. Для каждого подмножества вычисляется суммарный объем (столбец с заголовком) и сверяется с вместимостью рюкзака. Если выбранное подмножество предметов помещается в рюкзак (суммарный объем предметов не превышает вместимости рюкзака), то для выбранных предметов рассчитывается суммарная стоимость (столбец). Окончательным решением задачи будет подмножество предметов, имеющее максимальную суммарную стоимость при допустимом суммарном объеме. На рис. 6 строка, соответствующая решению, отмечена рамкой.

14:

Пример реализации функции knapsack_s на языке C++, которая решает задачу о рюкзаке.

// Knapsack.h #pragma once #include "Combi.h" int knapsack_s( int V,// [in] вместимость рюкзака short n,// [in] количество типов предметов const int v[],// [in] размер предмета каждого типа const int c[],// [in] стоимость предмета каждого типа short m[]// [out] количество предметов каждого типа );

Рис.7. Прототип функции knapsack_s

15-16:

// Knapsack.cpp #include "stdafx.h" #include "Knapsack.h" #define NINF 0x80000000// самое малое int-число int calcv(combi::subset s, const int v[])// объем в рюкзаке { int rc = 0; for (int i = 0; i < s.sn; i++) rc += v[s.ntx(i)]; return rc; }; int calcc(combi::subset s, const int v[], const int c[])//стоимость в рюкзаке { int rc = 0; for (int i = 0; i < s.sn; i++) rc += (v[s.ntx(i)]*c[s.ntx(i)]); return rc; }; void setm(combi::subset s, short m[])//отметить выбранные предметы { for (int i = 0; i < s.n; i++) m[i] = 0; for (int i = 0; i < s.sn; i++) m[s.ntx(i)] = 1; }; int knapsack_s( int V,// [in] вместимость рюкзака short n,// [in] количество типов предметов const int v[],// [in] размер предмета каждого типа const int c[],// [in] стоимость предмета каждого типа short m[]// [out] количество предметов каждого типа {0,1} ) { combi::subset s(n); int maxc = NINF, cc = 0; short ns = s.getfirst(); while (ns >= 0) { if (calcv(s, v) <= V) if ((cc = calcc(s,v,c)) > maxc) { maxc = cc; setm(s,m); } ns = s.getnext(); }; return maxc; };

Рис.8. Реализация функции knapsack_s

Функция knapsack_s имеет четыре входных параметра, задающих условие задачи: V (объем рюкзака), n (количество предметов), v (массив размерностью n, содержащий объемы всех предметов), c (массив размерностью n, содержащий стоимости всех предметов), а также один выходной параметр m (массив размерностью n). Каждый элемент массива m может быть только единицей или нулем. Единица указывает, что соответствующий предмет включен, а ноль – не включен в оптимальный перечень предметов. В результате выполнения функция возвращает оптимальную стоимость рюкзака, т. е. максимальную суммарную стоимость предметов, которые можно одновременно поместить в рюкзак заданной вместимости.

В процессе своей работы функция knapsack_s использует генератор множества всех подмножеств (combi::subset) и вызывает три вспомогательные функции: calcv, calcc и setm.

Для подключения генератора в заголовочный файл функции knapsack_s (рис. 7)добавлена директива include, которая включает файл Combi.h, содержащий шаблон структуры combi::subset.

Функция calcv предназначена для вычисления суммарного объема текущего подмножества предметов. Она принимает два входных параметра: s (структуру combi::subset) и v (массив размерностью n, содержащий объемы всех предметов), а также возвращает суммарный объем текущего подмножества предметов.

Функция calcс позволяетвычислить суммарную стоимость текущего подмножества предметов. Онапринимает два входных параметра: s (структуру combi::subset) и c (массив размерностью n, содержащий стоимости всех предметов), а возвращает суммарную стоимость текущего подмножества предметов.

Функция setm принимает два параметра: входной s (структуру combi::subset) и возвращаемый m ( массив размерностью n, содержащий нули и единицы).

Функция knapsack_s перебирает все подмножества множества предметов (функции getfirst и getnext генератора), вычисляет суммарный объем (функция calcv) каждого подмножества, для подмножества с суммарным объемом, меньшим V, рассчитывает суммарную стоимость (функция calcc) и запоминает (и возвращает) оптимальный вариант (формирует выходной массив m спомощьюфункции setm).

17-19:

Пример вызова функции knapsack_s для решения задачи о рюкзаке с исходными данными для схемы, представленной на рис. 6.

// Main #include "stdafx.h" #include <iostream> #include "Combi.h" #include "Knapsack.h" #define NN 4 int _tmain(int argc, _TCHAR* argv[]) { setlocale(LC_ALL, "rus"); int V = 100,// вместимость рюкзака v[] = {25, 30, 60, 20},// размер предмета каждого типа c[] = {25, 10, 20, 30};// стоимость предмета каждого типа short m[NN];// количество предметов каждого типа {0,1} int maxcc = knapsack_s( V,// [in] вместимость рюкзака NN,// [in] количество типов предметов v,// [in] размер предмета каждого типа c,// [in] стоимость предмета каждого типа m// [out] количество предметов каждого типа ); std::cout<<std::endl<<"-------- Задача о рюкзаке --------- "; std::cout<<std::endl<<"- количество предметов: "<< NN; std::cout<<std::endl<<"- вместимость рюкзака: "<< V; std::cout<<std::endl<<"- размеры предметов: "; for(int i = 0; i < NN; i++) std::cout<<v[i]<<" "; std::cout<<std::endl<<"- стоимости предметов: "; for(int i = 0; i < NN; i++) std::cout<<v[i]*c[i]<<" "; std::cout<<std::endl<<"- оптимальная стоимость рюкзака: " << maxcc; std::cout<<std::endl<<"- вес рюкзака: "; int s = 0; for(int i = 0; i < NN; i++) s+= m[i]*v[i]; std::cout<<s; std::cout<<std::endl<<"- выбраны предметы: "; for(int i = 0; i < NN; i++) std::cout<<" "<<m[i]; std::cout<<std::endl<<std::endl; system("pause"); return 0; }

Рис. 9. Пример использования функции knapsack_s

Рис. 10. Результат выполнения программы, представленной на рис. 9

20-21:

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

// Main #include "stdafx.h" #include <iostream> #include "Combi.h" #include "Knapsack.h" #include <time.h> #include <iomanip> #define NN (sizeof(c)/sizeof(int)) int _tmain(int argc, _TCHAR* argv[]) { setlocale(LC_ALL, "rus"); int V = 600,// вместимость рюкзака v[] = {25, 56, 67, 40, 20, 27, 37, 33, 33, 44, 53, 12, 60, 75, 12, 55, 54, 42, 43, 14, 30, 37, 31, 12}, c[] = {15, 26, 27, 43, 16, 26, 42, 22, 34, 12, 33, 30, 12, 45, 60, 41, 33, 11, 14, 12, 25, 41, 30, 40}; short m[NN]; int maxcc = 0; clock_t t1, t2; std::cout<<std::endl<<"-------- Задача о рюкзаке --------- "; std::cout<<std::endl<<"- вместимость рюкзака: "<< V; std::cout<<std::endl<<"-- количество ------ продолжительность -- "; std::cout<<std::endl<<" предметов вычисления "; for (int i = 14; i <= NN; i++) { t1 = clock(); maxcc = knapsack_s(V, i, v, c, m); t2 = clock(); std::cout<<std::endl<<" "<<std::setw(2)<<i <<" "<<std::setw(5)<<(t2-t1); } std::cout<<std::endl<<std::endl; system("pause"); return 0; }

Рис. 11. Вычисление продолжительности решения задачи о рюкзаке при различном количестве предметов

Для вычисления продолжительности выполнения функции knapsack_s в программе используется стандартная функция clock, возвращающая количество условных единиц времени, прошедших с момента запуска программы. Разница между возвращаемыми значениями функции clock,полученными до вызова knapsack_s и после, позволяет оценить продолжительность выполнения этой функции.

22:

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

Рис. 12. Результат выполнения программы, представленной на рис. 11

23:

График, построенный по результатам выполнения программы. Несложно заметить, что с увеличением количества предметов (параметр n функции knapsack_s) наединицу продолжительность выполнения функции knapsack_s удваивается. Такой результат согласуется с оценкой сложности алгоритма генерации булеана множества мощности n.

Зависимость продолжительности вычисления

от размерности задачи о рюкзаке

0.00

5.00

10.00

15.00

20.00

25.00

30.00

35.00

Количество предметов

Продолжительность

вычисления, с

Рис. 13. Зависимость продолжительности выполнения функции knapsack_s от значения ее параметра n

Эксперимент (рис. 12 и 13) проводился на компьютере с процессором Pentium V с тактовой частотой 3,2 ГГц. Простая экстраполяция результатов этого эксперимента дает следующие результаты: для 30 предметов продолжительность вычисления будет составлять более 24 мин., для 40 – более 16 сут., а для 45 – почти два года.

24:

Дата добавления: 2014-01-20