2014-02-02
1709
Применение генератора сочетаний продемонстрируем на решении задачи об оптимальной загрузке судна. Сформулируем условие задачи.
На палубе судна имеется мест для размещения стандартных контейнеров. Выбрать n контейнеров для погрузки на судно можно из имеющихся в наличии. Каждый контейнер характеризуется весом и доходом от его перевозки. Необходимо выбрать контейнеров таким образом, чтобы их общий вес не превышал но при этом доход от перевозки был максимально возможным.
Математическая модель задачи может быть записана следующим образом:
,
где – неизвестные (номера выбранных контейнеров), которые требуется найти.
Решением задачи будет вектор Каждый элемент этого вектора может принимать целое значение из отрезка и при этом все значения должны быть разными.
34:
Схема решения задачи с применением генератора подмножеств. Задача имеет следующие исходные данные:
– ограничение по общему весу контейнеров;
– количество контейнеров;
– количество свободных мест на палубе;
– вес контейнеров;
– доход от перевозки контейнеров.
Рис. 19. Схема решения задачи об оптимальной загрузке судна
Строки таблицы, озаглавленной на рис. 19 символом представляют собой все сочетания по три из множества. Эти сочетания могут быть получены с помощью соответствующего генератора. Несложно убедиться, что количество строк составляет а порядок их перечисления соответствует порядку генерации сочетаний, рассмотренным выше алгоритмом.
Используя элементы сгенерированных сочетаний в качестве индексов для массивов (вес каждого контейнера) и (доход от перевозки), осуществляется выбор соответствующих значений (вторая таблица слева на рис. 19), что позволяет рассчитать вес (столбец) и доход от перевозки (столбец) комбинации контейнеров. Решением задачи будет сочетание контейнеров, имеющее максимальный суммарный доход при допустимом суммарном весе. На рис. 19 строка, соответствующая решению, отмечена рамкой.
35:
пример реализации на языке С++ функции boat,решающей задачу об оптимальной загрузке судна.
| // --- Вoat.h // -- решение задачи об оптимальной загрузке судна // функция возвращает доход от перевози выбранных контейнеров #pragma once #include "Combi.h" int boat( int V,// [in] максимальный вес груза short m,// [in] количество мест для контейнеров short n,// [in] всего контейнеров const int v[],// [in] вес каждого контейнера const int c[],// [in] доход от перевозки каждого контейнера short r[]// [out] результат: индексы выбранных контейнеров ); |
Рис. 20. Функция boat, решающая задачу об оптимальной загрузке судна
Функция boat имеет пять входных параметров, определяющих условие задачи: V (максимальный допустимый суммарный вес контейнеров), m (количество мест на палубе для установки контейнеров), n (общее количество контейнеров), v (массив размерностью n, содержащий вес каждого контейнера), c (массив размерностью n, содержащий доход от перевозки каждого контейнера), а также один возвращаемый параметр r (массив размерностью m, содержащий номера выбранных контейнеров). В том случае, если решение существует, функция boat возвращает положительное значение, иначе – нуль.
36-37:
В процессе своей работы функция boat использует генератор сочетаний (combi::xcombination) и вызывает три вспомогательные функции: boatfnc::calcv (расчет веса текущего сочетания контейнеров), boatfnc::calcс (расчет дохода от транспортировки текущего сочетания контейнеров) и boatfnc::copycomb (копирование текущей компинации).
| // --- Вoat.cpp #include "stdafx.h" #include "Boat.h" namespace boatfnc { int calcv(combi::xcombination s, const int v[])// вес { int rc = 0; for (int i = 0; i < s.m; i++) rc += v[s.ntx(i)]; return rc; }; int calcc(combi::xcombination s, const int c[])// доход { int rc = 0; for (int i = 0; i < s.m; i++) rc += c[s.ntx(i)]; return rc; }; void copycomb(short m, short *r1, const short *r2)// копировать { for (int i = 0; i < m; i++) r1[i] = r2[i]; }; } int boat( int V,// [in] максимальный вес груза short m,// [in] количество мест для контейнеров short n,// [in] всего контейнеров const int v[],// [in] вес каждого контейнера const int c[],// [in] доход от перевозки каждого контейнера short r[]// [out] результат: индексы выбранных контейнеров ) { combi::xcombination xc(n, m); int rc = 0, i = xc.getfirst(), cc = 0; while (i > 0) { if (boatfnc::calcv(xc,v)<= V) if ((cc = boatfnc::calcc(xc,c)) > rc) {rc = cc; boatfnc::copycomb(m, r, xc.sset);} i = xc.getnext(); }; return rc; }; |
Рис. 21. Реализация функции boat
Функция boat последовательно генерирует все возможные сочетания по m контейнеров, вычисляет для каждого сочетания суммарный вес(функция boatfnc::calcv), для сочетаний с весом, не превышающим допустимое значение V,вычисляетдоход от перевозки этих контейнеров (boatfnc::calcс), фиксирует оптимальную комбинацию контейнеров (boatfnc::copycomb)и возвращает оптимальную доходность или нуль, если решения нет.
38-40:
Пример вызова функции boat для решения задачи.
| // --- Main #include "stdafx.h" #include <iostream> #include <iomanip> #include "Boat.h" #define NN (sizeof(v)/sizeof(int)) #define MM 3 int _tmain(int argc, _TCHAR* argv[]) { setlocale(LC_ALL, "rus"); int V = 1000, v[] = {100, 200, 300, 400, 500, 150}, c[NN] = { 10, 15, 20, 25, 30, 25}; short r[MM]; int cc = boat( V,// [in] максимальный вес груза MM,// [in] количество мест для контейнеров NN,// [in] всего контейнеров v,// [in] вес каждого контейнера c,// [in] доход от перевозки каждого контейнера r// [out] результат: индексы выбранных контейнеров ); std::cout<<std::endl<<"- Задача о размещении контейнеров на судне"; std::cout<<std::endl<<"- общее количество контейнеров: "<< NN; std::cout<<std::endl<<"- количество мест для контейнеров: "<< MM; std::cout<<std::endl<<"- ограничение по суммарному весу: "<< V; std::cout<<std::endl<<"- вес контейнеров: "; for(int i = 0; i < NN; i++) std::cout<<std::setw(3)<<v[i]<<" "; std::cout<<std::endl<<"- доход от перевозки: "; for(int i = 0; i < NN; i++) std::cout<<std::setw(3)<<c[i]<<" "; std::cout<<std::endl<<"- выбраны контейнеры (0,1,...,m-1): "; for(int i = 0; i < MM; i++) std::cout<<r[i]<<" "; std::cout<<std::endl<<"- доход от перевозки: " << cc; std::cout<<std::endl<<"- общий вес выбранных контейнеров: "; int s = 0; for(int i = 0; i < MM; i++) s+= v[r[i]]; std::cout<<s; std::cout<<std::endl<<std::endl; system("pause"); return 0; } |
Рис. 22. Пример решения задачи об оптимальной загрузке судна
Рис. 23. Результат выполнения программы, представленной на рис. 3.7
41-42:
Представлена программа, с помощью которой можно оценить продолжительность решения задачи о загрузке судна при разном количестве контейнеров. В программе фиксируется значение параметра m (количество мест для контейнеров) и вычисляется продолжительность работы функции boat в зависимости от параметра n (общее количество контейнеров).
| // --- Main #include "stdafx.h" #include <iostream> #include <iomanip> #include "Boat.h" #include <time.h> #define NN (sizeof(v)/sizeof(int)) #define MM 6 #define SPACE(n) std::setw(n)<<" " int _tmain(int argc, _TCHAR* argv[]) { setlocale(LC_ALL, "rus"); int V = 1000, v[] = {250, 560, 670, 400, 200, 270, 370, 330, 330, 440, 530, 120, 200, 270, 370, 330, 330, 440, 700, 120, 550, 540, 420, 170, 600, 700, 120, 550, 540, 420, 430, 140, 300, 370, 310, 120}; int c[NN]={15,26, 27, 43, 16, 26, 42, 22, 34, 12, 33, 30, 42,22, 34, 43, 16, 26, 14, 12, 25, 41, 17, 28, 12,45, 60, 41, 33, 11, 14, 12, 25, 41, 30, 40}; short r[MM]; int maxcc = 0; clock_t t1, t2; std::cout<<std::endl<<"-- Задача об оптимальной загрузке судна -- "; std::cout<<std::endl<<"- ограничение по весу: "<< V; std::cout<<std::endl<<"- количество мест: "<< MM; std::cout<<std::endl<<"-- количество ------ продолжительность -- "; std::cout<<std::endl<<" контейнеров вычисления "; for (int i = 24; i <= NN; i++) { t1 = clock(); int maxcc = boat(V, MM, i, v, c, r); t2 = clock(); std::cout<<std::endl<<SPACE(7)<<std::setw(2)<<i <<SPACE(15)<<std::setw(5)<<(t2-t1); } std::cout<<std::endl<<std::endl; system("pause"); return 0; } |
Рис. 24. Вычисление продолжительности решения задачи о загрузке судна при разном количестве контейнеров
Как и в задаче о рюкзаке, для вычисления продолжительности выполнения функции boat в программе, применяется стандартная функция clock.
43-44:
Рис. 25. Результат работы программы, представленной на рис. 24
| Зависимость продолжительности вычисления |
| от количества контейнеров |
| 0.00 |
| 0.10 |
| 0.20 |
| 0.30 |
| 0.40 |
| 0.50 |
| 0.60 |
| 0.70 |
| 0.80 |
| Количество контейнеров |
| Продолжительность |
| вычисления, с |
Рис. 26. Зависимость продолжительности выполнения функции boat от значения параметра n
Вид графика на рис. 26 согласуется с оценкой сложности алгоритма генерации сочетаний по 6 элементов из множества мощности
