Материал: Информационная система поддержки принятия решений в условиях многокритериальной оптимизации

) мультипликативная свёртка: f = exp (α₁ln (K₁) +…+α_nln (K_n)) = =11. nnKKαα;

) приведенная свёртка: f = min (K_i/α_i) по всем i=1…n (или f = max (K_i/α_i) по всем i=1…n).

Аксиоматические методы построения функции полезности - это формальные методы, основанные на том, что формулируются специальные предположения (аксиомы) о свойствах предпочтения, выполнение которых гарантирует существование функции полезности конкретного вида.

Обычно, при использовании таких методов функцию полезности строят в аддитивном виде:

= λ₁f₁+…+λ_nf_{n (}*)

как сумму функций полезности по каждому критерию с некоторыми весовыми коэффициентами λ₁,…,λ_n.

Пусть K_I ⊂ K = {K₁,…,K_n} - подмножество множества критериев, т.е. группа критериев с номерами из множества I = {i₁,…, i_m}. Ī = {1,…,n}\I. Тогда K_{Ī -} все остальные критерии, а векторная оценка x представляется в виде (x_I,x_Ī).

Говорят, что критерии K_I не зависят по предпочтению от критериев K_Ī, если предпочтения для любых двух оценок x = (x_I,x_Ī) и x’ = (x_I’,x_Ī), содержащих одинаковые компоненты с номерами из Ī, не зависят от самих значений этих компонент.

Критерии K₁,…,K_n такие, что любой набор K_I из них не зависит по предпочтению от остальных критериев K_Ī, называются взаимно независимыми по предпочтению.

Теорема Дебре (критерий существования аддитивной функции полезности): функция полезности может быть задана в аддитивном виде (*) тогда и только тогда, когда критерии K₁,…,K_n взаимно независимы по предпочтению (при n≥3).

При n=2, кроме взаимной независимости критериев, требуется выполнение условия соответственных замещений (при n≥3 оно выполняется автоматически):

∀x₁,x₂,y₁,y₂,a,b,c,d если (x₁,x₂) ∼ (x₁-a,x₂+b) и (x₁,y₂) ∼ (x₁-a,y₂+c), то (y₁,x₂) ∼ (y₁-d,x₂+b) и (y₁,y₂) ∼ (y₁-d,y₂+c).

Т.е., если увеличение на b и c разных значений x₂ и y₂ критерия K₂ при некотором опорном значении x₁ критерия K₁ компенсируется одним и тем же уменьшением этого значения x₁ критерия K₁, то такие же увеличения b и c тех же значений x₂ и y₂ критерия K₂ сохраняются и при любом другом опорном значении y₁ критерия K₁.

Как осуществляется проверка взаимной независимости критериев по предпочтению?

Непосредственно по определению проверить независимость критериев затруднительно, т.к. даже при небольших n возникает большое число вариантов, которые надо проверить.

Утверждение (Леонтьева-Гормана): если любая пара критериев { K_i, K_j } не зависит по предпочтению от остальных (n-2) критериев, то все критерии K₁,…,K_n взаимно независимы по предпочтению.

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

Пусть необходимо проверить на независимость по предпочтению наборы K_I и K_Ī. Берём набор x_Ī⁺ наилучших (явно хороших) значений K_Ī и подбираем (запрашиваем у ЛПР) два разных набора x_I’ и x_I’’ таких, что (x_I’, x_Ī⁺) ~ (x_I’’, x_Ī⁺). Затем берём набор x_Ī ^- самых плохих оценок и спрашиваем у ЛПР, сохранилось ли безразличие (x_I’, x_Ī^-) ~ (x_I’’, x_Ī^-)? Если нет, то критерии K_I зависят от критериев K_Ī. Если да, повторяем процедуру еще для некоторых других x_I’ и x_I’’. Если всё время безразличие остаётся, задаём вопрос в общем виде (сохранится ли безразличие при любых наборах). Если да, то наборы критериев K_I и K_Ī независимы.

Методы построения аддитивной функции полезности

Шаговый метод совместного шкалирования.

Пусть n=2 и условие соответственных замещений выполнено.

(x₁,x₂) = f₁ (x₁) + f₂ (x₂) ∀ (x₁,x₂) ∈X.

Обозначим диапазоны изменения оценок x₁ и x₂: x_1* ≤ x₁ ≤ x₁^*, x_2* ≤ x₂ ≤ x₂^*.

Полагаем f (x_1*,x_2*) = f₁ (x_1*) = f₂ (x_2*) = 0 (начало отсчета).

Берем любое значение x₁¹ > x_1* достаточно близкое к нему. Устанавливаем f₁ (x₁¹) = 1 (единица измерения).

От ЛПР требуем указать x₂¹ такое, что (x₁¹, x_2*) ~ (x_1*, x₂¹), для этого значения также f₁ (x₂¹) = 1.

Затем у ЛПР запрашиваем x₁² и x₂² такие, что:

(x₁², x_2*) ~ (x₁¹, x₂¹) ~ ~ (x_1*, x₂²). f (x₁¹,x₂¹) = 1+1 = 2 ⇒ f₁ (x₁²) = f₂ (x₂²) = 2.

Далее у ЛПР запрашиваем x₁³ и x₂³ такие, что:

(x₁³, x_2*) ~ (x₁², x₂¹) ~ ~ (x₁¹, x₂²) ~ (x_1*, x₂³) ⇒ f₁ (x₁³) = f₂ (x₂³) = 3.

И т.д. Таким образом, получаем наборы значений f₁ (x_1*), f₁ (x₁¹), f₁ (x₁²), f₁ (x₁³) … и f₂ (x_2*), f₂ (x₂¹), f₂ (x₂²), f₁ (x₂³) … по которым с помощью интерполяции строятся функции f₁ (x) и f₂ (x).

Метод половинного деления.

Метод находит функцию полезности в виде

(x₁,x₂) = λ₁f₁ (x₁) +λ₂f₂ (x₂), где f₁ (x_1*) = f₂ (x_2*) = 0, f₁ (x₁^*) = f₂ (x₂^*) = 1, λ₁>0, λ₂>0, λ₁+λ₂=1.

Построим функцию f₁.

ЛПР просим указать среднюю по полезности оценку x₁^0.5 ∈ [x_1*; x₁^*], т.е. такую, изменение полезности на [x_1*; x₁^0.5] равно изменению полезности на [x₁^0.5; x₁^*]. Устанавливаем f₁ (x₁^0.5) = 0.5.

Далее аналогично получаем

₁^0.25 ∈ [x_1*; x₁^0.5] ⇒ f₁ (x₁^0.25) = 0.25 и x₁^0.75 ∈ [x₁^0.5; x₁^*] ⇒ f₁ (x₁^0.75) = 0.75 и т.д.

С помощью интерполяции, восстанавливаем функцию f₁ по её значениям в точках x₁^0.5, x₁^0.25, x₁^0.75…

Функция f₂ строится аналогично.

Для нахождения весового коэффициента λ₁ достаточно запросить у ЛПР пару одинаковых по предпочтительности оценок (x₁’,x₂’) ∼ (x₁’’,x₂’’) ⇒ ⇒ f (x₁’,x₂’) = f (x₁’’,x₂’’) ⇒ λ₁f₁ (x₁’) + (1-λ₁) f₂ (x₂’) = λ₁f₁ (x₁’’) + (1-λ₁) f₂ (x₂’’), а из этого равенства уже можно выразить λ_{1 (}а λ₂ = 1 - λ₁).

4. Слои Парето

Поскольку вероятность того, что исходное множество будет одновременно являться и множеством Парето (состоять из несравнимых объектов) крайне мала, то будем выделять т. н. слои Парето. Один слой формируется следующим образом:

из исходного множества выделяется недоминируемый элемент

затем выделяются все несравнимые с ним объекты

Выделенные объекты заносятся в новое множество, называемое слоем Парето. Затем исходное множество, из которого теперь удалены "лучшие" объекты, обрабатывается по тому же принципу до тех пор, пока обработке и занесению в свой слой не подвергнется каждый его элемент. Каждый слой Парето является элементом множества подмножеств исходного множества. На рис.4.1 показан граф, иллюстрирующий пример отношения доминирования на множестве. Исходящая стрелка обозначает доминирование объекта, из которого она исходит, над объектом, на который она указывает. Двунаправленная стрелка говорит о том, что объекты несравнимы (4 ó 14, 8 ó 13). Узел 5 является доминирующим на исходном множестве, поэтому на рисунке он не имеет ни одной входящей стрелки, в т. ч. двунаправленной, а только исходящие. Поэтому его можно выделить во множество (слой) Парето, которое будет состоять только из одного элемента. На рисунках 4.2 - 4.8 показан процесс изменения исходного множества по мере выделения из него слоёв Парето.

Рис.4.1 В центре расположен недоминируемый объект (узел графа).

 

Рис.4.2.

 

Рис.4.3.

 

Рис.4.4.

 

Рис.4.5.

 

Рис.4.6.

 

Рис.4.7                                                                        Рис.4.8

 

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

[5]

[7]

[17]

[16]

[12]

[4] [8] [13] [14]

[10] [15] [20]

[1] [2] [3] [6] [9] [11] [18] [19]

Сравнение упаковки объектов для сортировки по полезности и для распределения по слоям Парето.

В таблице 4.1 представлены объекты, отсортированные по полезности:

 

Таблица 4.1 Сортировка по полезности.

№ объекта	Значение функции полезности
5	15
7	14
8	12
13	12
16	12
4	11
9	11
12	11
14	11
15	11
2	10
19	10
20	10
6	9
10	9
18	9
1	8
3	8
11	8

Упакуем объекты в контейнеры, отсортировав их по полезности (Таб.4.2)

Таблица 4.2 Распределение объектов по контейнерам после сортировки по полезности.

Номера контейнеров	1	2	3	4	5
Номера объектов	5, 7, 8	17, 16	13, 9, 12	4, 14	15, 2

Величина суммарной полезности: 144.

А теперь упакуем их после распределения по слоям Парето (Таб.4.3)

 

Таблица 4.3 Распределение объектов по контейнерам после распределения по слоям Парето.

Номера контейнеров12345
Номера объектов	5, 7, 8	17, 16	13, 9, 12	4, 14	15, 2

Величина суммарной полезности: 120.

На рис. 4.9 представлен график, отображающий результаты упаковки для обоих случаев распределения объектов. Вывод.

Рис. 4.9 Представление результатов упаковки.

 

Вывод.

Была выполнена упаковка 20 объектов, каждый из которых имеет свои характеристики массы и объёма. Упаковка производилась в 5 контейнеров двумя способами: по полезности и по слоям Парето. В обоих случаях количество упакованных объектов одинаково. Оценка результатов упаковки для варианта по слоям Парето в данной задаче оказалась хуже, чем для упаковки по полезности.

 

5. Программа

Структура

Программа, решающая эту задачу, написана на языке Java. Java является объектно-ориентированным языком, поэтому в нём доступны классы - структуры данных, описывающие объекты. С математической точки зрения класс можно отождествить с вектором, а поля класса - со скалярами в составе этого вектора. При этом поля класса могут сами являться объектами (экземплярами) других классов (или этого же класса, в случае со связными списками). Помимо этого, класс содержит методы, позволяющие оперировать данными. Другими словами, поля описывают объект класса, а методы - поведение этого объекта. Java также поддерживает спецификаторы доступа к полям и методам, что позволяет обезопасить данные внутри класса от нежелательного доступа и модификации ("повреждения информации"). Также в Java существует наследование классов - объект класса-наследника наследует поля и методы родительского класса, за исключением приватных. Этот механизм используется в случае, когда существующий класс недостаточно подробно описывает какой-либо объект, и требуется расширить его описание и/или переопределить методы родительского класса, доступные классу-наследнику. Класс в Java может наследоваться только от одного родительского класса - создатели языка пришли к выводу, что во всех случаях, когда в программе используется множественное наследование, можно перестроить архитектуру программы так, чтобы обойтись одиночным. Это намного упрощает разработку и исключает проблему т. н. "ромбовидного наследования".

Помимо обычного наследования, в Java есть механизм интерфейсов. Интерфейс можно описать как класс, все поля которого являются константами, а все методы - абстрактными. Интерфейс не содержит реализаций методов, аналогично прототипам функций в С/С++. Интерфейсы, как и классы, могут наследоваться друг от друга, причём для них возможно множественное наследование (поскольку методы в интерфейсах не реализованы, проблем с "ромбовидным наследованием" не возникает). Для задействования механизма интерфейсов в объявлении класса нужно указать, что он реализует интерфейс с таким-то именем. После этого в этом классе необходимо реализовать все методы, объявленные в интерфейсе. Если реализация всех методов невозможна, а "пустые" реализации по тем или иным причинам недопустимы, можно объявить этот класс абстрактным. Но в этом случае объект этого класса, как и объект интерфейса, создать будет нельзя. Класс может реализовать любое количество интерфейсов, и интерфейс может быть реализован любым количеством классов. В дальнейшем, создав интерфейсную ссылку, её можно будет инициализировать объектом любого класса, реализующего этот интерфейс. При этом классы, реализующие интерфейс, могут не состоять друг с другом в каком-либо отношении наследования. (Благодаря этому можно, например, создать массив интерфейсных ссылок на такие классы). Через интерфейсную ссылку недоступны никакие поля объекта, которым инициализирована эта ссылка, кроме констант интерфейса, и недоступны никакие методы, не объявленные в этом интерфейсе либо в родительских интерфейсах. Механизм интерфейсов удобен в тех случаях, когда необходимо определить, что будет делать объект, и неважно, как именно он это будет делать, что очень помогает на стадии проектирования программы.

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

.        Количество элементов коллекции можно изменять, в то время как размер массива постоянен.

2.      Следовательно, на момент создания коллекции необязательно знать, сколько элементов должно быть в её составе. Тем более что это и не всегда возможно.

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

В данной программе определены классы, описывающие следующие сущности:

1.      Упаковываемый объект. Этот класс содержит параметры упаковываемых объектов - объём, вес и оценки по полезности.

2.      Контейнер. Описывает одномерный контейнер.

3.      Упаковщик. Осуществляет операции по созданию парных объектов, формированию слоёв Парето, упаковке объектов в контейнеры.

4.      ЛПР. Содержит алгоритм вычисления ценности (функция ценности), умеет сравнивать объекты по полезности, отображать парные объекты в один объект.

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

6.      Бинарное отношение (интерфейс). Содержит один метод - compare ("сравнить"). Реализован вложенным классом в классе, описывающем ЛПР.

Также имеется один класс, содержащий метод main, в котором реализована последовательность действий описываемых сущностей от момента создания всех объектов и до момента упаковки объектов.

 

 

Пример решения задачи

Рассмотрим следующую задачу:

Имеем 40 объектов. Объекты имеют два физических параметра - вес и объем, ценность объекта оценивается по пяти критериям. Причём оценки по двум критериям (критерий 1 и 2) более важны, чем оценки по другим критериям. Вычислим полезность каждого объекта. Воспользуемся прямым методом оценки многомерных альтернатив, тогда функция полезности каждого объекта будет иметь следующий вид:

где wi - вес i-го критерия, назначаемый ЛПР:- оценка альтернативы по i - му критерию.- число номеров критериев.

Назначим веса критериев, в соответствии с условием нормировки:

Так как критерий 1 и 2 имеют большую важность, то им будет соответствовать большой вес.

Вес критериев приведён в таблице 5.3.1.

Таблица 5.3.1 Веса критериев

№ критерия	Вес критерия, wi
1	0,45
2	0,45
3	0,04
4	0,04
5	0,02

На рис. 5.3.1 приведены характеристики объектов и контейнеров. На этом этапе есть возможность создавать и разбивать пары объектов, а также менять их характеристики и характеристики контейнеров.

Рис. 5.3.1 Объекты и контейнеры.

На рис. 5.3.2 приведены сформированные слои Парето, выделенные из исходного множества на основании предпочтений ЛПР. Объекты внутри слоёв отсортированы по полезности. Полезность объекта при упаковке прямо пропорциональна значениям оценок по критериям и обратно пропорциональна массе и объёму.

Рис. 5.3.2 Слои Парето, отсортированные по полезности.

 

На рис. 5.3.3 показаны слои Парето, отсортированные по объёму и массе.

Рис. 5.3.3 Слои Парето, отсортированные по объёму и массе.

 

Результаты упаковки для сортировки по полезности и по объёму и массе показаны на рисунках 5.3.4 и 5.3.5 соответственно.

Рис. 5.3.4 Результат упаковки при сортировке по полезности.

 

Рис. 5.3.5 Результат упаковки при сортировке по объёму и весу.

 

Заключение

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

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

Список использованных источников

1.      Ногин В.Д. Принятие решений в многокритериальной среде: количественный подход, М.: ФИЗМАТЛИТ, 2004, 176с.

2.      Ларичев О.И. Объективные модели и субъективные решения. М.: Изд-во "Наука", 1987. 480с.

.        П. Ноутон, Г. Шилдт Java 2 в подлиннике, БХВ-Петербург, 2008 г., 1072 стр.

Приложения

 

Приложение 1

 

Классы предметной области.

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

Класс "Упаковываемый объект". Параметры этого класса - ID, объём, вес, оценки по пяти критериям и ссылка на парный объект.

/**

* Упаковываемый объект.

* @author AtemB

*

*/ class Item {

/** ID. */id;

/** Объём. */

int volume;

/** Вес. */

int weight;

/** Критерий 1. */

int rate1;

/** Критерий 2. */

int rate2;

/** Критерий 3. */

int rate3;

/** Критерий 4. */

int rate4;

/** Критерий 5. */

int rate5;

/** Ссылка на парный объект. */

private Item pair;

public Item (String id,

int volume,

int weight,

int rate1,int rate2,int rate3,int rate4,int rate5) {

super ();

this. id = id;

this. volume = volume;

this. weight = weight;

this. rate1 = rate1;

this. rate2 = rate2;

this. rate3 = rate3;

this. rate4 = rate4;

this. rate5 = rate5;

}

/***/

public Item () {

this. id = 0 + "";

this. volume = 0;

this. weight = 0;

this. rate1 = 0;

this. rate2 = 0;

this. rate3 = 0;

this. rate4 = 0;

this. rate5 = 0;

}

public String getId () {

return id;

}

public Item getPair () {

return pair;

}

public void setPair (Item pair) {

this. pair = pair;

}

public boolean hasPair () {

return pair! = null;

}

/**

* @return the volume

*/

public int getVolume () {

return volume;

}

/**

* @return the weight

*/

public int getWeight () {

return weight;

}

/**

* @return the rate1

*/

public int getRate1 () {

return rate1;

}

/**

* @return the rate2

*/

public int getRate2 () {

return rate2;

}

/**

* @return the rate3

*/

public int getRate3 () {

return rate3;

}

/**

* @return the rate4

*/

public int getRate4 () {

return rate4;

}

/**

* @return the rate5

*/

public int getRate5 () {

return rate5;

}

/**

* @param volume the volume to set

*/

public void setVolume (int volume) {

this. volume = volume;

}

/**

* @param weight the weight to set

*/

public void setWeight (int weight) {

this. weight = weight;

}

/**

* @param rate1 the rate1 to set

*/

public void setRate1 (int rate1) {

this. rate1 = rate1;

}

/**

* @param rate2 the rate2 to set

*/

public void setRate2 (int rate2) {

this. rate2 = rate2;

}

/**

* @param rate3 the rate3 to set

*/

public void setRate3 (int rate3) {

this. rate3 = rate3;

}

/**

* @param rate4 the rate4 to set

*/

public void setRate4 (int rate4) {

this. rate4 = rate4;

}

/**

* @param rate5 the rate5 to set

*/

public void setRate5 (int rate5) {

this. rate5 = rate5;

}

/* (non-Javadoc)

* @see java. lang. Object#equals (java. lang. Object)

*/

@Override

public boolean equals (Object obj) {

if (this == obj) {

return true;

}

if (obj == null) {

return false;

}

if (! (obj instanceof Item)) {

return false;

}other = (Item) obj;

if (rate1! = other. rate1) {

return false;

}

if (rate2! = other. rate2) {

return false;

}

if (rate3! = other. rate3) {

return false;

}

if (rate4! = other. rate4) {

return false;

}

if (rate5! = other. rate5) {

return false;

}

if (volume! = other. volume) {

return false;

}

if (Double. doubleToLongBits (weight)! = Double

. doubleToLongBits (other. weight)) {

return false;

}

return true;

}

@Override

public Item clone () {clone = new Item (id, volume, weight, rate1, rate2, rate3, rate4, rate5);

return clone;

}

/* (non-Javadoc)

* @see java. lang. Object#toString ()

*/

@Override

public String toString () {

return "Объект" +

"\nID: " + id + ",\nОбъём: " + volume + ",\nВес: " + weight

+ ",\nКр.1: " + rate1 + ",\nКр.2: " + rate2 + ",\nКр.3: " + rate3

+ ",\nКр.4: " + rate4 + ",\nКр.5" + rate5 + ",\nID парного объекта: " + pair. id;

}

Класс "Контейнер". Его параметры - это ID, объём и грузоподъёмность.

/**

* Контейнер.

* @author AtemB

*

*/

public class Container {

/** ID. */

private int id;

/** Объём. */

private int volume;

/** Грузоподъёмность. */

private int cargo;

public Container (int id, int volume, int cargo) {

this. id = id;

this. volume = volume;

this. cargo = cargo;

}

public int getVolume () {

return volume;

}

public int getCargo () {

return cargo;

}

public int getId () {

return id;

}

/**

* @param volume the volume to set

*/

public void setVolume (int volume) {

this. volume = volume;

}

/**

* @param cargo the cargo to set

*/

public void setCargo (int cargo) {

this. cargo = cargo;

}

/**

* @param id the id to set

*/

public void setId (int id) {

this. id = id;

}

@Override

public Container clone () {clone = new Container (id, volume, cargo);

return clone;

}

/* (non-Javadoc)

* @see java. lang. Object#toString ()

*/

@Override

public String toString () {

return "Контейнер" +

",\nID: " + id +

"\nОбъём: " + volume +

",\nГрузоподъёмность: " + cargo;

}

}

Класс ЛПР. У этого класса всего одно поле - список весов критериев, используемая им при расчёте полезности объекта. ЛПР умеет сравнивать объекты, используя вложенный класс "Бинарное отношение", умеет отображать пару объектов в один объект и получать значение полезности любого объекта. Для ЛПР в данном случае полезность объекта прямо пропорциональна значениям оценок по критериям объекта и обратно пропорциональна его массе и объёму.

/**

* ЛПР (лицо, принимающее решения).

* @author AtemB

*

*/

public class Boss {

class BossBinaryRelation implements BinaryRelation<Item> {

@Override

public Item compare (Item i1, Item i2) {

// Конечно, не самая пряморукая реализация, зато относительно понятна для восприятия.

// В этот список заносятся разности оценок по критериям.<Double> rates = new LinkedList<Double> ();. add ( (double) (i1. rate1 - i2. rate1));. add ( (double) (i1. rate2 - i2. rate2));

// Флаги в этом списке означают, положителен или отрицателен

// результат сравнения критериев.

// Одинаковые значения в список не заносятся.<Boolean> flags = new LinkedList<Boolean> ();

for (Double d: rates) {

if (d. doubleValue () > 0) {. add (true);

} else if (d. doubleValue () < 0) {. add (false);

}

}

// Если спиок флагов пуст, значит, объекты по проверяемым критериям равны.

if (flags. isEmpty ()) {

return null;

} else {

boolean resultFlag = false;

for (int i = 1; i < flags. size (); i++) {= flags. get (i);

// Если в списке встречаются разные значения флагов, значит,

// объекты несравнимы по значимым критериям

// (один лучше по одним критериям, другой по другим).

if (flags. get (i - 1)! = flags. get (i)) {

return null;

}

}

// Если предыдущий цикл выполнился до конца, значит,

// один из объектов оказался лучше другого.

// Проверяем значение результирующего флага

// и возвращаем доминирующий объект.

if (resultFlag) {

return i1;

} else {

return i2;

}

}

}

}

private List<Double> weights;

public Boss () {= new ArrayList<Double> ();

{. add (0.45);. add (0.45);. add (0.04);. add (0.04);. add (0.02);

}

}

/**

* Получить полезность объекта.

* @param i Объект.

* @return Оценка объекта.

*/

public double getUtility (Item i) {

double ratesSum = i. rate1 * weights. get (0) +. rate2 * weights. get (1) +. rate3 * weights. get (2) +. rate4 * weights. get (3) +. rate5 * weights. get (4);

return ratesSum / i. weight / i. volume; // ( (i. weight + i. volume) / 2);

}

/**

* Отобразить пару объектов в один объект.

* @param i Любой объект из пары.

* @return Результирующий объект.

*/

public static Item mapPair (Item i) {first = i;second = i. getPair ();resultItem = new Item (first. id + ": " + second. id,. volume + second. volume,. weight + second. weight,. rate1 + second. rate1,first. rate2 + second. rate2,first. rate3 + second. rate3,first. rate4 + second. rate4,first. rate5 + second. rate5);

return resultItem;

}

/**

* Получить бинарное отношение, определённое ЛПР.

* @return Бинарное отношение.

public BinaryRelation<Item> getBinaryRelation () {

return new BossBinaryRelation ();

}

}

Класс "Склад". Его поля - список упаковываемых объектов, список контейнеров, сформированные слои Парето (при создании объекта это поле равно null), карта упакованных объектов и остаток, представляющий из себя список объектов. Также есть поле типа java. math. Random, использующееся при инициализации упаковываемых объектов и контейнеров.

/**

* Склад.

* @author AtemB

*

*/

public class Store {

class MapKeysComparator implements Comparator<Container> {

@Override

public int compare (Container c1, Container c2) {

return c1. getId () - c2. getId ();

}

}

private List<Item> items;

private List<Container> containers;

private Random r = new Random ();

private List<List<Item>> paretoSet;

private SortedMap<Container, List<Item>> map;

private List<Item> rest;

public Store () {= new ArrayList<Container> ();= new ArrayList<Item> ();= new ArrayList<Item> ();= new TreeMap<Container, List<Item>> (new MapKeysComparator ());

}

public void createContainers (int containersNum, ContainerTemplate ct, int maxVolume, int maxCargo) {r = new Random ();

int volumeDiapasonLength = maxVolume - ct. getVolume (). getBegin ();

int cargoDiapasonLength = maxCargo - ct. getCargo (). getBegin ();

for (int i = 0; i < containersNum; i++) {. add (new Container (i,. nextInt (volumeDiapasonLength + 1) + ct. getVolume (). getBegin (),. nextInt (cargoDiapasonLength + 1) + ct. getCargo (). getBegin ()));

}

for (Container c: containers) {. put (c, new LinkedList<Item> ());

}

}

public void createItems (int itemsNum, ItemTemplate it, int maxVolume, int maxWeight) {

int volumeDiapasonLength = maxVolume - it. getVolume (). getBegin ();

int weightDiapasonLength = maxWeight - it. getWeight (). getBegin ();

int r1DiapasonLength = it. getRate1 (). getEnd () - it. getRate1 (). getBegin ();

int r2DiapasonLength = it. getRate2 (). getEnd () - it. getRate2 (). getBegin ();

int r3DiapasonLength = it. getRate3 (). getEnd () - it. getRate3 (). getBegin ();

int r4DiapasonLength = it. getRate4 (). getEnd () - it. getRate4 (). getBegin ();

int r5DiapasonLength = it. getRate5 (). getEnd () - it. getRate5 (). getBegin ();

for (int i = 0; i < itemsNum; i++) {. add (new Item (i + "", r. nextInt (volumeDiapasonLength + 1) + it. getVolume (). getBegin (),. nextInt (weightDiapasonLength + 1) + it. getWeight (). getBegin (),. nextInt (r1DiapasonLength + 1) + it. getRate1 (). getBegin (),. nextInt (r2DiapasonLength + 1) + it. getRate2 (). getBegin (),. nextInt (r3DiapasonLength + 1) + it. getRate3 (). getBegin (),. nextInt (r4DiapasonLength + 1) + it. getRate4 (). getBegin (),. nextInt (r5DiapasonLength + 1) + it. getRate5 (). getBegin ()));

}

}

/**

* @return the containers

*/

public List<Container> getContainers () {

return containers;

}

/**

* @return the items

*/

public List<Item> getItemsClones () {<SimpleEntry<String, String>> itemPairs = new ArrayList<SimpleEntry<String, String>> ();<Item> newItems = new ArrayList<Item> ();

for (Item i: items) {. add (i. clone ());

if (i. hasPair ()) {. add (new SimpleEntry<String, String> (i. getId (), i. getPair (). getId ()));

}

}

for (Entry<String, String> e: itemPairs) {(e. getKey (), newItems). setPair (getItemFromListByID (e. getValue (), newItems));

}

return newItems;

}

public List<Item> getItemsInstance () {

return items;

}

public void setEmpty () {. clear ();. clear ();

}

/**

* @return the paretoSet

*/

public List<List<Item>> getParetoSetInstance () {

return paretoSet;

}

/**

* @return the paretoSet

*/

public List<List<Item>> getParetoSetClone () {<List<Item>> clone = new ArrayList<List<Item>> ();<SimpleEntry<String, String>> itemPairs = new ArrayList<SimpleEntry<String, String>> ();

for (List<Item> paretoLayer: paretoSet) {<Item> newParetoLayer = new ArrayList<Item> ();

for (Item i: paretoLayer) {. add (i. clone ());

if (i. hasPair ()) {. add (new SimpleEntry<String, String> (i. getId (), i. getPair (). getId ()));

}

}. add (newParetoLayer);

}

for (Entry<String, String> e: itemPairs) {(e. getKey (), clone). setPair (getItemFromParetoSetByID (e. getValue (), clone));

}

return clone;

}

/**

* @param paretoSet the paretoSet to set

*/

public void setParetoSet (List<List<Item>> paretoSet) {

this. paretoSet = paretoSet;

}

private Item getItemFromListByID (String id, List<Item> items) {

for (Item i: items) {

if (i. getId (). equals (id)) {

return i;

}

}

return null;

}

private Item getItemFromParetoSetByID (String id, List<List<Item>> paretoSet) {

for (List<Item> items: paretoSet) {

for (Item i: items) {

if (i. getId (). equals (id)) {

return i;

}

}

}

return null;

}

/**

* @return the map

*/

public SortedMap<Container, List<Item>> getMapInstance () {

return map;

}

/**

* @return the map

*/

public SortedMap<Container, List<Item>> getMapClone () {<Container, List<Item>> clone = new TreeMap<Container, List<Item>> (new MapKeysComparator ());<Entry<Container, List<Item>>> set = map. entrySet ();

for (Entry<Container, List<Item>> e: set) {<Item> items = new ArrayList<Item> ();

for (Item i: e. getValue ()) {. add (i. clone ());

}. put (e. getKey (). clone (), items);

}

return clone;

}

/**

* @param map the map to set

*/

public void setMap (SortedMap<Container, List<Item>> map) {

this. map = map;

}

public boolean paretoSetIsEmpty () {

boolean result = false;

return result;

}

/**

* @return the rest

*/

public List<Item> getRest () {

return rest;

}

/**

* @param rest the rest to set

*/

public void setRest (List<Item> rest) {

this. rest = rest;

}

}

Класс Упаковщик. Поля этого класса - ЛПР и Склад. Также в нём объявлены два перечисления, в которых указаны тип сортировки объектов и алгоритм упаковки. Этот класс оперирует с упаковываемыми объектами на основе информации ЛПР (обрабатывает парные объекты, создаёт слои Парето), сортирует указанным образом, и упаковывает объекты.

/**

* Упаковщик.

* @author AtemB

*

*/

public class Packer {

/**

* Алгоритм упаковки.

* @author AtemB

*

*/

public enum ALGORYTHM {

/** В первый подходящий. */

FIRST,

/** В первый подходящий с убыванием. */

FIRST_DECREASE,

/** В лучший из подходящих. */

BEST,

/** В лучший из подходящих с убыванием. */

BEST_DECREASE

}

/**

* Тип сортировки.

* @author AtemB

*

*/

public enum SORT_TYPE {

/** По весу. */

WEIGHT,

/** По объёму. */

VOLUME,

/** По полезности. */

UTILITY,

/** По величине. */

SIZE

}

private Store store;

private Boss boss;

public Packer (Store store, Boss boss) {

this. store = store;

this. boss = boss;

}

public void breakPair (Item i1, Item i2) {. setPair (null);. setPair (null);

}

public void createPair (Item i1, Item i2) {. setPair (i2);. setPair (i1);

}

/**

* Обработать парные объекты.

* @param items Исходное множество объектов.

* @return Результирующее множество объектов.

*/

public List<Item> processPairs (List<Item> items) {<Item> listForRemove = new ArrayList<Item> ();

// Отображаем все пары в монолитные объекты.

for (int i = 0; i < items. size (); i++) {current = items. get (i);

if (current. hasPair ()) {

// Помещаем парный текущему объект в список на удаление,

// т.к. теперь его параметры будут отражены в результирующем объекте.. add (current. getPair ());resultItem = Boss. mapPair (current);

// Замещаем исходный объект по текущему индексу результирующим.. set (i, resultItem);. getPair (). setPair (null);

}

}

// Удаляем парные объекты из списка.

for (Item i: listForRemove) {. remove (i);

}

return items;

}

/**

* Создать слой Парето.

* @param boss ЛПР.

* @param items Исходное множество.

* @return Слой парето.

*/

public List<Item> extractParetoLayer (List<Item> items) {<Item> relation = boss. getBinaryRelation ();

if (items. isEmpty ()) {

return null;

} else {

// Сначала извлекаем первый попавшийся недоминируемый объект на исходном множестве.<Item> bestItems = new ArrayList<Item> ();best = items. get (0);

for (Item i: items) {

// Сравниваем текущий элемент с каждым из элементов последовательности.

// Если новый элемент лучше текущего - инициализируем им ссылку на лучший объект.

if (relation.compare (best, i) == i) {= i;

}

}

// Удаляем недоминируемый объект из исходного множества.. remove (best);

// Добавляем его в слой Парето.. add (best);

// Теперь нужно найти все несравнимые с ним элементы исходного множества.<Item> equalItems = new ArrayList<Item> ();

for (Item i: items) {

// Если очередной элемент несравним с ранее полученным лучшим,

// добавляем его в результирующее множество.

if (relation.compare (best, i) == null) {. add (i);

}

}

// Удаляем из исходного множества все ссылки на недоминируемые объекты.

for (Item i: equalItems) {. remove (i);

}

// Добавляем недоминируемые объекты в слой Парето.

for (Item i: equalItems) {. add (i);

}

return bestItems;

}

}

/**

* Получить множества (слои) Парето.

* @param boss ЛПР.

* @param items Исходное множество.

* @return Слои Парето.

*/

public List<List<Item>> createParetoSet (List<Item> items) {<List<Item>> layers = new ArrayList<List<Item>> ();

while (! (items. isEmpty ())) {<Item> paretoLayer = extractParetoLayer (items);. add (paretoLayer);

}

return layers;

}

/**

* Упаковать очередной слой Парето. Инкапсулирует логику алгоритма упаковки.

* @param map Карта, содержащая информацию о контейнерах и об упакованных объектах.

* @param paretoLayer Слой Парето.

* @return Ту же карту с очередным добавленным слоем.

*/

public SortedMap<Container, List<Item>> pack (SortedMap<Container, List<Item>> map, List<Item> paretoLayer, ALGORYTHM algorythm) {

// Получаем массу и объём слоя Парето.

double layerWeight = 0.0;

double layerVolume = 0.0;

for (Item i: paretoLayer) {+= i. weight;+= i. volume;

}

if (algorythm == ALGORYTHM. FIRST_DECREASE || algorythm == ALGORYTHM. BEST_DECREASE) {(paretoLayer, SORT_TYPE. SIZE);

}

// Если он в полном составе не упаковывается, его нужно сортировать по эффективности.

if (layerWeight > getFreeCargo (map) ||> getFreeSpace (map)) {(paretoLayer, Packer. SORT_TYPE. UTILITY);

}<Item> forRemove = new ArrayList<Item> ();

for (Item item: paretoLayer) {

if (! tryToPack (map, item, algorythm)) {. getRest (). add (item);. add (item);

}

}

for (Item i: forRemove) {. remove (i);

}

return map;

}

/**

* Попробовать паковать объект.

* @param map

* @param item Объект.

* @return Флаг удачного завершения операции.

*/

private boolean tryToPack (SortedMap<Container, List<Item>> map, Item item, ALGORYTHM algorythm) {<Container> containers = map. keySet ();

if (algorythm == ALGORYTHM. BEST || algorythm == ALGORYTHM. BEST_DECREASE) {bestContainer = getBest (containers, item, map);

if (bestContainer == null) {

return false;

} else {. get (bestContainer). add (item);

return true;

}

}

for (Container container: containers) {

if (canPack (container, item, map)) {. get (container). add (item);

return true;

}

}

return false;

}

/**

* Получить свободное место в контейнерах.

* @param map Карта, содержащая информацию о контейнерах и об упакованных объектах.

* @return Свободное место.

*/

private double getFreeSpace (SortedMap<Container, List<Item>> map) {

double freeSpace = 0.0;

for (Container c: map. keySet ()) {

double itemsVolume = 0.0;

for (Item i: map. get (c)) {+= i. volume;

}+= (c. getVolume () - itemsVolume);

}

return freeSpace;

}

/**

* Получить оставшуюся грузоподъёмность контейнеров.

* @param map Карта, содержащая информацию о контейнерах и об упакованных объектах.

* @return Оставшуюся грузоподъёмность контейнеров.

*/

private double getFreeCargo (SortedMap<Container, List<Item>> map) {

double freeCargo = 0.0;

for (Container c: map. keySet ()) {

double itemsWeight = 0.0;

for (Item i: map. get (c)) {+= i. weight;

}+= (c. getCargo () - itemsWeight);

}

return freeCargo;

}

/**

* Проверить возможность упаковки объекта в контейнер.

* @param c Контейнер.

* @param i Объект.

* @param map Карта, содержащая информацию об упакованных объектах.

* @return Флаг проверки.

*/

private boolean canPack (Container c, Item i, SortedMap<Container, List<Item>> map) {

// Получаем список объектов, упакованных в этот контейнер.<Item> items = map. get (c);

int totalVolume = 0;

double totalWeight = 0.0;

// Получаем суммарный вес и объём объектов, упакованных в этот контейнер.

for (Item item: items) {+= item. volume;+= item. weight;

}

// больше оставшейся грузоподъёмности

// или свободного места в контейнере,

// объект в него упаковать нельзя.

if (c. getVolume () - totalVolume < i. volume ||. getCargo () - totalWeight < i. weight) {

return false;

}

return true;

}

/**

* Создать парные объекты на исходном множестве.

* @param pairsNum Необходимое количество пар.

* @param items Исходное множество.

*/

public void createPairs (int pairsNum, List<Item> items) {r = new Random ();

int pairCounter = 0;

while (pairCounter < pairsNum) {(items. get (r. nextInt (items. size ())), items);= countPairs (items);

}

}

/**

* Найти парный объект.

* @param i Объект, для которого ищется парный объект.

* @param items Исходное множество.

*/

private void findPair (Item i, List<Item> items) {

if (! (i. hasPair ())) {r = new Random ();pair;

do {= items. get (r. nextInt (items. size ()));

} while (pair. hasPair () || pair == i);. setPair (pair);. setPair (i);

}

}

/**

* Сосчитать парные объекты.

* @param items Исходное множество.

* @return Количество пар.

*/

public int countPairs (List<Item> items) {

int pairsCounter = 0;

for (Item i: items) {

if (i. hasPair ()) {++;

}

}

return pairsCounter / 2;

}

/**

* Извлечь наиболее тяжёлый объект. <p>

* Полученный объект удаляется из списка.

* @param items Список объектов.

* @return Самый тяжёлый объект.

*/

public Item extractHardest (List<Item> items) {hardest = items. get (0);

for (Item i: items) {

if (i. weight > hardest. weight) {= i;

}

}. remove (hardest);

return hardest;

}

/**

* Извлечь наиболее объёмный объект. <p>

* Полученный объект удаляется из списка.

* @param items Список объектов.

* @return Самый объёмный объект.

*/

public Item extractLargest (List<Item> items) {largest = items. get (0);

for (Item i: items) {

if (i. volume > largest. volume) {= i;

}

}. remove (largest);

return largest;

}

public void sort (List<Item> items, SORT_TYPE. template) {

int itemsSize = items. size ();

int templateLength = template. length;

for (int i = 0; i < itemsSize; i++) {_TYPE type = template [i % templateLength];

for (int j = i; j < itemsSize; j++) {

for (int k = i; k < itemsSize; k++) {

switch (type) {

case VOLUME:

if (items. get (j). volume < items. get (k). volume) {buffer = items. get (j);. set (j, items. get (k));. set (k, buffer);

}

break;

case WEIGHT:

if (items. get (j). weight < items. get (k). weight) {buffer = items. get (j);. set (j, items. get (k));. set (k, buffer);

}

break;

case UTILITY:

if (boss. getUtility (items. get (j)) < boss. getUtility (items. get (k))) {buffer = items. get (j);. set (j, items. get (k));. set (k, buffer);

}

break;

case SIZE:

if (countSize (items. get (j)) > countSize (items. get (k))) {buffer = items. get (j);. set (j, items. get (k));. set (k, buffer);

}

break;

default:

break;

}

}

}

}

}

/**

* Рассчитать размер. Расчёт производится по массе и объёму.

* @param i Объект.

*/

private double countSize (Item i) {

return i. volume * i. weight;

}

/**

* Получить лучший контейнер из подходящих. <p>

* Лучшим контейнер с минимальным свободным местом (грузоподъёмность или объём) под упаковку объекта.

* @param containers Контейнеры.

* @param i Объект.

* @param map Карта упаковки.

* @return Лучший контейнер.

*/

private Container getBest (Collection<Container> containers, Item i, SortedMap<Container, List<Item>> map) {

return getValid (getValidContainers (containers, i, map), i, map);

}

/**

* Получить контейнеры, пригодные для упаковки объекта.

* @param containers Контейнеры.

* @param i Объект.

* @param map Карта упаковки.

* @return Список контейнеров, в которые можно упаковать объект.

*/

private List<Container> getValidContainers (Collection<Container> containers, Item i, SortedMap<Container, List<Item>> map) {<Container> validContainers = new ArrayList<Container> ();

for (Container c: containers) {

if (canPack (c, i, map)) {. add (c);

}

}

return validContainers;

}

/**

* Получить контейнер, в котором осталось наименьшее количество места для упаковки объекта.

* @param containers Контейнеры.

* @param i Объект.

* @param map Карта упаковки.

* @return Контейнер.

*/

private Container getValid (List<Container> containers, Item i, SortedMap<Container, List<Item>> map) {

double minimalRests = 0;

for (Container c: containers) {

double rests = getRests (c, i, map);

if (rests > minimalRests) {+= rests;

}

}

for (Container c: containers) {

double rests = getRests (c, i, map);

if (rests == 0) {

return c;

}

if (rests < minimalRests) {= rests;

}

}

for (Container c: containers) {

if (getRests (c, i, map) == minimalRests) {

return c;

}

}

return null;

}

/**

* Получить остаток. <p>

* Остатком считается наименьшее значение из остатка по грузоподъёмности или остатка по объёму.

* @param c Контейнер.

* @param i Объект.

* @param map Карта упаковки.

* @return Остаток.

*/

private double getRests (Container c, Item i, SortedMap<Container, List<Item>> map) {

double totalVolume = 0;

double totalWeight = 0;

for (Item item: map. get (c)) {+= item. volume;+= item. weight;

}

double volumeRests = c. getVolume () - totalVolume;

double cargoRests = c. getCargo () - totalWeight;

if (volumeRests < cargoRests) {

return volumeRests;

} else if (cargoRests < volumeRests) {

return cargoRests;

}

return 0;

}

}

Также в программе присутствуют классы графического интерфейса и отдельный класс, содержащий метод main ().

Полный исходный код программы.

Исходный код программы на Java.

Пакет core.. java

package core;

/**

* Бинарное отношение.

* @author AtemB

*

* @param <T> Тип элементов множества.

*/

public interface BinaryRelation<T> {

/**

* Сравнить два элемента множества. Этот метод инкапсулирует логику бинарного отношения.

* @param t1 Первый элемент.

* @param t2 Второй элемент.

* @return Доминирующий элемент или null, если элементы несравнимы.

*/

public T compare (T t1, T t2);

}. java

package core;

import java. util. ArrayList;

import java. util. LinkedList;

import java. util. List;

import java. util. Map;

/**

* ЛПР (лицо, принимающее решения).

* @author AtemB

*

*/

public class Boss {

class BossBinaryRelation implements BinaryRelation<Item> {

@Override

public Item compare (Item i1, Item i2) {

// Конечно, не самая пряморукая реализация, зато относительно понятна для восприятия.

// В этот список заносятся разности оценок по критериям.<Double> rates = new LinkedList<Double> ();. add ( (double) (i1. rate1 - i2. rate1));. add ( (double) (i1. rate2 - i2. rate2));

// Флаги в этом списке означают, положителен или отрицателен

// результат сравнения критериев.

// Одинаковые значения в список не заносятся.<Boolean> flags = new LinkedList<Boolean> ();

for (Double d: rates) {

if (d. doubleValue () > 0) {. add (true);

} else if (d. doubleValue () < 0) {. add (false);

}

}

// Если спиок флагов пуст, значит, объекты по проверяемым критериям равны.

if (flags. isEmpty ()) {

return null;

} else {

boolean resultFlag = false;

for (int i = 1; i < flags. size (); i++) {= flags. get (i);

// Если в списке встречаются разные значения флагов, значит,

// объекты несравнимы по значимым критериям

// (один лучше по одним критериям, другой по другим).

if (flags. get (i - 1)! = flags. get (i)) {

return null;

}

}

// Если предыдущий цикл выполнился до конца, значит,

// один из объектов оказался лучше другого.

// Проверяем значение результирующего флага

// и возвращаем доминирующий объект.

if (resultFlag) {

return i1;

} else {

return i2;

}

}

}

}

private List<Double> weights;

public Boss () {= new ArrayList<Double> ();

{. add (0.45);. add (0.45);. add (0.04);. add (0.04);. add (0.02);

}

}

/**

* Получить полезность объекта.

* @param i Объект.

* @return Оценка объекта.

*/

public double getUtility (Item i) {

double ratesSum = i. rate1 * weights. get (0) +. rate2 * weights. get (1) +. rate3 * weights. get (2) +. rate4 * weights. get (3) +. rate5 * weights. get (4);

return ratesSum / i. weight / i. volume;

}

private double getCriterialUtility (Item i) {

return i. rate1 * weights. get (0) +. rate2 * weights. get (1) +. rate3 * weights. get (2) +. rate4 * weights. get (3) +. rate5 * weights. get (4);

}

/**

* Отобразить пару объектов в один объект.

* @param i Любой объект из пары.

* @return Результирующий объект.

*/

public static Item mapPair (Item i) {first = i;second = i. getPair ();resultItem = new Item (first. id + ": " + second. id,. volume + second. volume,. weight + second. weight,. rate1 + second. rate1,first. rate2 + second. rate2,first. rate3 + second. rate3,first. rate4 + second. rate4,first. rate5 + second. rate5);

return resultItem;

}

/**

* Получить бинарное отношение, определённое ЛПР.

* @return Бинарное отношение.

*/

public BinaryRelation<Item> getBinaryRelation () {

return new BossBinaryRelation ();

}

public double getPackUtility (Map<Container, List<Item>> map) {

double utility = 0;

for (Container c: map. keySet ()) {

for (Item i: map. get (c)) {+= getCriterialUtility (i);

}

}

return utility;

}

}. java

package core;

/**

* Контейнер.

* @author AtemB

*

*/

public class Container {

/** ID. */

private int id;

/** Объём. */

private int volume;

/** Грузоподъёмность. */

private int cargo;

public Container (int id, int volume, int cargo) {

this. id = id;

this. volume = volume;

this. cargo = cargo;

}

public int getVolume () {

return volume;

}

public int getCargo () {

return cargo;

}

public int getId () {

return id;

}

/**

* @param volume the volume to set

*/

public void setVolume (int volume) {

this. volume = volume;

}

/**

* @param cargo the cargo to set

*/

public void setCargo (int cargo) {

this. cargo = cargo;

}

/**

* @param id the id to set

*/

public void setId (int id) {

this. id = id;

}

@Override

public Container clone () {clone = new Container (id, volume, cargo);

return clone;

}

/* (non-Javadoc)

* @see java. lang. Object#toString ()

*/

@Override

public String toString () {

return "Контейнер" +

",\nID: " + id +

"\nОбъём: " + volume +

",\nГрузоподъёмность: " + cargo;

}

package core;

/**

* Упаковываемый объект.

* @author AtemB

*

*/

public class Item {

/** ID. */id;

/** Объём. */

int volume;

/** Вес. */

int weight;

/** Критерий 1. */

int rate1;

/** Критерий 2. */

int rate2;

/** Критерий 3. */

int rate3;

/** Критерий 4. */

int rate4;

/** Критерий 5. */

int rate5;

/** Ссылка на парный объект. */

private Item pair;

public Item (String id,

int volume,

int weight,

int rate1,int rate2,int rate3,int rate4,int rate5) {

super ();

this. id = id;

this. volume = volume;

this. weight = weight;

this. rate1 = rate1;

this. rate2 = rate2;

this. rate3 = rate3;

this. rate4 = rate4;

this. rate5 = rate5;

}

/***/

public Item () {

this. id = 0 + "";

this. volume = 0;

this. weight = 0;

this. rate1 = 0;

this. rate2 = 0;

this. rate3 = 0;

this. rate4 = 0;

this. rate5 = 0;

}

public String getId () {

return id;

}

public Item getPair () {

return pair;

}

public void setPair (Item pair) {

this. pair = pair;

}

public boolean hasPair () {

return pair! = null;

}

/**

* @return the volume

*/

public int getVolume () {

return volume;

}

/**

* @return the weight

*/

public int getWeight () {

return weight;

}

/**

* @return the rate1

*/

public int getRate1 () {

return rate1;

}

/**

* @return the rate2

*/

public int getRate2 () {

return rate2;

}

/**

* @return the rate3

*/

public int getRate3 () {

return rate3;

}

/**

* @return the rate4

*/

public int getRate4 () {

return rate4;

}

/**

* @return the rate5

*/

public int getRate5 () {

return rate5;

}

/**

* @param volume the volume to set

*/

public void setVolume (int volume) {

this. volume = volume;

}

/**

* @param weight the weight to set

*/

public void setWeight (int weight) {

this. weight = weight;

}

/**

* @param rate1 the rate1 to set

*/

public void setRate1 (int rate1) {

this. rate1 = rate1;

}

/**

* @param rate2 the rate2 to set

*/

public void setRate2 (int rate2) {

this. rate2 = rate2;

}

/**

* @param rate3 the rate3 to set

*/

public void setRate3 (int rate3) {

this. rate3 = rate3;

}

/**

* @param rate4 the rate4 to set

*/

public void setRate4 (int rate4) {

this. rate4 = rate4;

}

/**

* @param rate5 the rate5 to set

*/

public void setRate5 (int rate5) {

this. rate5 = rate5;

}

/* (non-Javadoc)

* @see java. lang. Object#equals (java. lang. Object)

*/

@Override

public boolean equals (Object obj) {

if (this == obj) {

return true;

}

if (obj == null) {

return false;

}

if (! (obj instanceof Item)) {

return false;

}other = (Item) obj;

if (rate1! = other. rate1) {

return false;

}

if (rate2! = other. rate2) {

return false;

}

if (rate3! = other. rate3) {

return false;

}

if (rate4! = other. rate4) {

return false;

}

if (rate5! = other. rate5) {

return false;

}

if (volume! = other. volume) {

return false;

}

if (Double. doubleToLongBits (weight)! = Double

. doubleToLongBits (other. weight)) {

return false;

}

return true;

}

@Override

public Item clone () {clone = new Item (id, volume, weight, rate1, rate2, rate3, rate4, rate5);

return clone;

}

/* (non-Javadoc)

* @see java. lang. Object#toString ()

*/

@Override

public String toString () {

return "Объект" +

"\nID: " + id + ",\nОбъём: " + volume + ",\nВес: " + weight

+ ",\nКр.1: " + rate1 + ",\nКр.2: " + rate2 + ",\nКр.3: " + rate3

+ ",\nКр.4: " + rate4 + ",\nКр.5" + rate5 + ",\nID парного объекта: " + pair. id;

}

}. java

package core;

import java. util. ArrayList;

import java. util. Collection;

import java. util. List;

import java. util. Random;

import java. util. Set;

import java. util. SortedMap;

/**

* Упаковщик.

* @author AtemB

*

*/

public class Packer {

/**

* Алгоритм упаковки.

* @author AtemB

*

*/

public enum ALGORYTHM {

/** В первый подходящий. */

FIRST,

// /** В первый подходящий с убыванием. */

// FIRST_DECREASE,

/** В лучший из подходящих. */

BEST,

// /** В лучший из подходящих с убыванием. */

// BEST_DECREASE

}

/**

* Тип сортировки.

* @author AtemB

*

*/

public enum SORT_TYPE {

/** По весу. */

WEIGHT,

/** По объёму. */

VOLUME,

/** По полезности. */

UTILITY,

/** По величине. */

SIZE

}

private Store store;

private Boss boss;

public Packer (Store store, Boss boss) {

this. store = store;

this. boss = boss;

}

public void breakPair (Item i1, Item i2) {. setPair (null);. setPair (null);

}

public void createPair (Item i1, Item i2) {. setPair (i2);. setPair (i1);

}

/**

* Обработать парные объекты.

* @param items Исходное множество объектов.

* @return Результирующее множество объектов.

*/

public List<Item> processPairs (List<Item> items) {<Item> listForRemove = new ArrayList<Item> ();

// Отображаем все пары в монолитные объекты.

for (int i = 0; i < items. size (); i++) {current = items. get (i);

if (current. hasPair ()) {

// Помещаем парный текущему объект в список на удаление,

// т.к. теперь его параметры будут отражены в результирующем объекте.. add (current. getPair ());resultItem = Boss. mapPair (current);

// Замещаем исходный объект по текущему индексу результирующим.. set (i, resultItem);. getPair (). setPair (null);

}

}

// Удаляем парные объекты из списка.

for (Item i: listForRemove) {. remove (i);

}

return items;

}

/**

* Создать слой Парето.

* @param boss ЛПР.

* @param items Исходное множество.

* @return Слой парето.

*/

public List<Item> extractParetoLayer (List<Item> items) {<Item> relation = boss. getBinaryRelation ();

if (items. isEmpty ()) {

return null;

} else {

// Сначала извлекаем первый попавшийся недоминируемый объект на исходном множестве.<Item> bestItems = new ArrayList<Item> ();best = items. get (0);

for (Item i: items) {

// Сравниваем текущий элемент с каждым из элементов последовательности.

// Если новый элемент лучше текущего - инициализируем им ссылку на лучший объект.

if (relation.compare (best, i) == i) {= i;

}

}

// Удаляем недоминируемый объект из исходного множества.. remove (best);

// Добавляем его в слой Парето.. add (best);

// Теперь нужно найти все несравнимые с ним элементы исходного множества.<Item> equalItems = new ArrayList<Item> ();

for (Item i: items) {

// Если очередной элемент несравним с ранее полученным лучшим,

// добавляем его в результирующее множество.

if (relation.compare (best, i) == null) {. add (i);

}

}

// Удаляем из исходного множества все ссылки на недоминируемые объекты.

for (Item i: equalItems) {. remove (i);

}

// Добавляем недоминируемые объекты в слой Парето.

for (Item i: equalItems) {. add (i);

}

return bestItems;

}

}

/**

* Получить множества (слои) Парето.

* @param boss ЛПР.

* @param items Исходное множество.

* @return Слои Парето.

*/

public List<List<Item>> createParetoSet (List<Item> items) {<List<Item>> layers = new ArrayList<List<Item>> ();

while (! (items. isEmpty ())) {<Item> paretoLayer = extractParetoLayer (items);. add (paretoLayer);

}

return layers;

}

/**

* Упаковать очередной слой Парето. Инкапсулирует логику алгоритма упаковки.

* @param map Карта, содержащая информацию о контейнерах и об упакованных объектах.

* @param paretoLayer Слой Парето.

* @return Ту же карту с очередным добавленным слоем.

*/

public SortedMap<Container, List<Item>> pack (SortedMap<Container, List<Item>> map, List<Item> paretoLayer, ALGORYTHM algorythm) {

// Получаем массу и объём слоя Парето.

double layerWeight = 0.0;

double layerVolume = 0.0;

for (Item i: paretoLayer) {+= i. weight;+= i. volume;

}

// if (algorythm == ALGORYTHM. FIRST_DECREASE || algorythm == ALGORYTHM. BEST_DECREASE) {

// sort (paretoLayer, SORT_TYPE. SIZE);

// }

// Если он в полном составе не упаковывается, его нужно сортировать по эффективности.

if (layerWeight > getFreeCargo (map) ||> getFreeSpace (map)) {(paretoLayer, Packer. SORT_TYPE. UTILITY);

}<Item> forRemove = new ArrayList<Item> ();

for (Item item: paretoLayer) {

if (! tryToPack (map, item, algorythm)) {. getRest (). add (item);. add (item);

}

}

for (Item i: forRemove) {. remove (i);

}

return map;

}

/**

* Попробовать паковать объект.

* @param map

* @param item Объект.

* @return Флаг удачного завершения операции.

*/

private boolean tryToPack (SortedMap<Container, List<Item>> map, Item item, ALGORYTHM algorythm) {<Container> containers = map. keySet ();

if (algorythm == ALGORYTHM. BEST/* || algorythm == ALGORYTHM. BEST_DECREASE*/) {bestContainer = getBest (containers, item, map);

return false;

} else {. get (bestContainer). add (item);

return true;

}

} else if (algorythm == ALGORYTHM. FIRST) {

for (Container container: containers) {

if (canPack (container, item, map)) {. get (container). add (item);

return true;

}

}

}

return false;

}

/**

* Получить свободное место в контейнерах.

* @param map Карта, содержащая информацию о контейнерах и об упакованных объектах.

* @return Свободное место.

*/

private double getFreeSpace (SortedMap<Container, List<Item>> map) {

double freeSpace = 0.0;

for (Container c: map. keySet ()) {

double itemsVolume = 0.0;

for (Item i: map. get (c)) {+= i. volume;

}+= (c. getVolume () - itemsVolume);

}

return freeSpace;

}

/**

* Получить оставшуюся грузоподъёмность контейнеров.

* @param map Карта, содержащая информацию о контейнерах и об упакованных объектах.

* @return Оставшуюся грузоподъёмность контейнеров.

*/

private double getFreeCargo (SortedMap<Container, List<Item>> map) {

double freeCargo = 0.0;

for (Container c: map. keySet ()) {

double itemsWeight = 0.0;

for (Item i: map. get (c)) {+= i. weight;

}+= (c. getCargo () - itemsWeight);

}

return freeCargo;

}

/**

* Проверить возможность упаковки объекта в контейнер.

* @param c Контейнер.

* @param i Объект.

* @param map Карта, содержащая информацию об упакованных объектах.

* @return Флаг проверки.

*/

private boolean canPack (Container c, Item i, SortedMap<Container, List<Item>> map) {

// Получаем список объектов, упакованных в этот контейнер.<Item> items = map. get (c);

int totalVolume = 0;

double totalWeight = 0.0;

// Получаем суммарный вес и объём объектов, упакованных в этот контейнер.

for (Item item: items) {+= item. volume;+= item. weight;

}

// Если масса или объём проверяемого объекта

// больше оставшейся грузоподъёмности

// или свободного места в контейнере,

// объект в него упаковать нельзя.

if (c. getVolume () - totalVolume < i. volume ||. getCargo () - totalWeight < i. weight) {

return false;

}

return true;

}

/**

* Создать парные объекты на исходном множестве.

* @param pairsNum Необходимое количество пар.

* @param items Исходное множество.

*/

public void createPairs (int pairsNum, List<Item> items) {r = new Random ();

int pairCounter = 0;

while (pairCounter < pairsNum) {(items. get (r. nextInt (items. size ())), items);= countPairs (items);

}

}

/**

* Найти парный объект.

* @param i Объект, для которого ищется парный объект.

* @param items Исходное множество.

*/

private void findPair (Item i, List<Item> items) {

if (! (i. hasPair ())) {r = new Random ();pair;

do {= items. get (r. nextInt (items. size ()));

} while (pair. hasPair () || pair == i);. setPair (pair);. setPair (i);

}

}

/**

* Сосчитать парные объекты.

* @param items Исходное множество.

* @return Количество пар.

*/

public int countPairs (List<Item> items) {

int pairsCounter = 0;

for (Item i: items) {

if (i. hasPair ()) {++;

}

}

return pairsCounter / 2;

}

/**

* Извлечь наиболее тяжёлый объект. <p>

* Полученный объект удаляется из списка.

* @param items Список объектов.

* @return Самый тяжёлый объект.

*/

public Item extractHardest (List<Item> items) {hardest = items. get (0);

for (Item i: items) {

if (i. weight > hardest. weight) {= i;

}

}. remove (hardest);

return hardest;

}

/**

* Извлечь наиболее объёмный объект. <p>

* Полученный объект удаляется из списка.

* @param items Список объектов.

* @return Самый объёмный объект.

*/

public Item extractLargest (List<Item> items) {largest = items. get (0);

for (Item i: items) {

if (i. volume > largest. volume) {= i;

}

}. remove (largest);

return largest;

}

public void sort (List<Item> items, SORT_TYPE. template) {

int itemsSize = items. size ();

int templateLength = template. length;

for (int i = 0; i < itemsSize; i++) {_TYPE type = template [i % templateLength];

for (int j = i; j < itemsSize; j++) {

for (int k = i; k < itemsSize; k++) {

switch (type) {

case VOLUME:

if (items. get (j). volume < items. get (k). volume) {buffer = items. get (j);. set (j, items. get (k));. set (k, buffer);

}

break;

case WEIGHT:

if (items. get (j). weight < items. get (k). weight) {buffer = items. get (j);. set (j, items. get (k));. set (k, buffer);

}

break;

case UTILITY:

if (boss. getUtility (items. get (j)) > boss. getUtility (items. get (k))) {buffer = items. get (j);. set (j, items. get (k));. set (k, buffer);

}

break;

case SIZE:

if (countSize (items. get (j)) > countSize (items. get (k))) {buffer = items. get (j);. set (j, items. get (k));. set (k, buffer);

}

break;

default:

break;

}

}

}

}

}

/**

* Рассчитать размер. Расчёт производится по массе и объёму.

* @param i Объект.

*/

private double countSize (Item i) {

return i. volume * i. weight;

}

/**

* Получить лучший контейнер из подходящих. <p>

* Лучшим контейнер с минимальным свободным местом (грузоподъёмность или объём) под упаковку объекта.

* @param containers Контейнеры.

* @param i Объект.

* @param map Карта упаковки.

* @return Лучший контейнер.

*/

private Container getBest (Collection<Container> containers, Item i, SortedMap<Container, List<Item>> map) {

return getValid (getValidContainers (containers, i, map), i, map);

}

/**

* Получить контейнеры, пригодные для упаковки объекта.

* @param containers Контейнеры.

* @param i Объект.

* @param map Карта упаковки.

* @return Список контейнеров, в которые можно упаковать объект.

*/

private List<Container> getValidContainers (Collection<Container> containers, Item i, SortedMap<Container, List<Item>> map) {<Container> validContainers = new ArrayList<Container> ();

for (Container c: containers) {

if (canPack (c, i, map)) {. add (c);

}

}

return validContainers;

}

/**

* Получить контейнер, в котором осталось наименьшее количество места для упаковки объекта.

* @param containers Контейнеры.

* @param i Объект.

* @param map Карта упаковки.

* @return Контейнер.

*/

private Container getValid (List<Container> containers, Item i, SortedMap<Container, List<Item>> map) {

double minimalRests = 0;

for (Container c: containers) {

double rests = getRests (c, i, map);

if (rests > minimalRests) {+= rests;

}

}

for (Container c: containers) {

double rests = getRests (c, i, map);

if (rests == 0) {

return c;

}

if (rests < minimalRests) {= rests;

}

}

for (Container c: containers) {

if (getRests (c, i, map) == minimalRests) {

return c;

}

}

return null;

}

/**

* Получить остаток. <p>

* Остатком считается наименьшее значение из остатка по грузоподъёмности или остатка по объёму.

* @param c Контейнер.

* @param i Объект.

* @param map Карта упаковки.

* @return Остаток.

*/

private double getRests (Container c, Item i, SortedMap<Container, List<Item>> map) {

double totalVolume = 0;

double totalWeight = 0;

for (Item item: map. get (c)) {+= item. volume;+= item. weight;

}

double volumeRests = c. getVolume () - totalVolume;

double cargoRests = c. getCargo () - totalWeight;

if (volumeRests < cargoRests) {

return volumeRests;

} else if (cargoRests < volumeRests) {

return cargoRests;

}

return 0;

}

}. java

package core;

import java. util. AbstractMap. SimpleEntry;

import java. util. ArrayList;

import java. util.comparator;

import java. util. LinkedList;

import java. util. List;

import java. util. Map. Entry;

import java. util. Random;

import java. util. Set;

import java. util. SortedMap;

import java. util. TreeMap;

import util. ContainerTemplate;

import util. ItemTemplate;

/**

* Склад.

* @author AtemB

*

*/

public class Store {

/**

* Сортировщик по ключам карты упаковки.

* @author AtemB

*

*/

class MapKeysComparator implements Comparator<Container> {

private List<Integer> template;

public MapKeysComparator (int index) {

this. template = templates. get (index);

}

@Override

public int compare (Container c1, Container c2) {

return template. indexOf (c1. getId ()) - template. indexOf (c2. getId ());

}

}

/** Упаковываемые объекты. */

private List<Item> items;

/** Контейнеры. */

private List<Container> containers;

/** Генератор псевдослучайных чисел. */

private Random r = new Random ();

/** Слои Парето. */

private List<List<Item>> paretoSet;

/** Карта упаковки. */

private SortedMap<Container, List<Item>> map;

/** Остаток. */

private List<Item> rest;

private int [] containersSequence;

private List<List<Integer>> templates;

public Store () {= new ArrayList<Container> ();= new ArrayList<Item> ();= new ArrayList<Item> ();

}

/**

* Создать контейнеры.

* @param containersNum Число контейнеров.

* @param ct Шаблон контейнера.

* @param maxVolume Ограничение по объёму.

* @param maxCargo Ограничение по грузоподъёмности.

*/

public void createContainers (int containersNum, ContainerTemplate ct, int maxVolume, int maxCargo) {r = new Random ();

int volumeDiapasonLength = maxVolume - ct. getVolume (). getBegin ();

int cargoDiapasonLength = maxCargo - ct. getCargo (). getBegin ();

for (int i = 0; i < containersNum; i++) {. add (new Container (i + 1,r. nextInt (volumeDiapasonLength + 1) + ct. getVolume (). getBegin (),. nextInt (cargoDiapasonLength + 1) + ct. getCargo (). getBegin ()));

}

this. containersSequence = new int [containersNum];

for (int i = 0; i < containersNum; i++) {[i] = containers. get (i). getId ();

}= new LinkedList<List<Integer>> ();(templates, containersSequence, containersNum);= new TreeMap<Container, List<Item>> (new MapKeysComparator (0));

for (Container c: containers) {. put (c, new LinkedList<Item> ());

}

}

/**

* Создать упаковываемые объекты.

* @param itemsNum Число объектов.

* @param it Шабло объекта.

* @param maxVolume Ограничение по объёму.

* @param maxWeight Ограничение по массе.

*/

public void createItems (int itemsNum, ItemTemplate it, int maxVolume, int maxWeight) {

int volumeDiapasonLength = maxVolume - it. getVolume (). getBegin ();

int weightDiapasonLength = maxWeight - it. getWeight (). getBegin ();

int r1DiapasonLength = it. getRate1 (). getEnd () - it. getRate1 (). getBegin ();

int r2DiapasonLength = it. getRate2 (). getEnd () - it. getRate2 (). getBegin ();

int r3DiapasonLength = it. getRate3 (). getEnd () - it. getRate3 (). getBegin ();

int r4DiapasonLength = it. getRate4 (). getEnd () - it. getRate4 (). getBegin ();

int r5DiapasonLength = it. getRate5 (). getEnd () - it. getRate5 (). getBegin ();

for (int i = 0; i < itemsNum; i++) {. add (new Item ( (i + 1) + "", r. nextInt (volumeDiapasonLength + 1) + it. getVolume (). getBegin (),. nextInt (weightDiapasonLength + 1) + it. getWeight (). getBegin (),. nextInt (r1DiapasonLength + 1) + it. getRate1 (). getBegin (),. nextInt (r2DiapasonLength + 1) + it. getRate2 (). getBegin (),. nextInt (r3DiapasonLength + 1) + it. getRate3 (). getBegin (),. nextInt (r4DiapasonLength + 1) + it. getRate4 (). getBegin (),. nextInt (r5DiapasonLength + 1) + it. getRate5 (). getBegin ()));

}

}

/**

* @return the containers

*/

public List<Container> getContainers () {

return containers;

}

/**

* @return the items

*/

public List<Item> getItemsClones () {<SimpleEntry<String, String>> itemPairs = new ArrayList<SimpleEntry<String, String>> ();<Item> newItems = new ArrayList<Item> ();

for (Item i: items) {. add (i. clone ());

if (i. hasPair ()) {. add (new SimpleEntry<String, String> (i. getId (), i. getPair (). getId ()));

}

}

for (Entry<String, String> e: itemPairs) {(e. getKey (), newItems). setPair (getItemFromListByID (e. getValue (), newItems));

}

return newItems;

}

public List<Item> getItemsInstance () {

return items;

}

public void setEmpty () {. clear ();. clear ();

}

/**

* @return the paretoSet

*/

return paretoSet;

}

/**

* @return the paretoSet

*/

public List<List<Item>> getParetoSetClone () {<List<Item>> clone = new ArrayList<List<Item>> ();<SimpleEntry<String, String>> itemPairs = new ArrayList<SimpleEntry<String, String>> ();

for (List<Item> paretoLayer: paretoSet) {<Item> newParetoLayer = new ArrayList<Item> ();

for (Item i: paretoLayer) {. add (i. clone ());

if (i. hasPair ()) {. add (new SimpleEntry<String, String> (i. getId (), i. getPair (). getId ()));

}

}. add (newParetoLayer);

}

for (Entry<String, String> e: itemPairs) {(e. getKey (), clone). setPair (getItemFromParetoSetByID (e. getValue (), clone));

}

return clone;

}

/**

* @param paretoSet the paretoSet to set

*/

public void setParetoSet (List<List<Item>> paretoSet) {

this. paretoSet = paretoSet;

}

private Item getItemFromListByID (String id, List<Item> items) {

for (Item i: items) {

if (i. getId (). equals (id)) {

return i;

}

}

return null;

}

private Item getItemFromParetoSetByID (String id, List<List<Item>> paretoSet) {

for (List<Item> items: paretoSet) {

for (Item i: items) {

if (i. getId (). equals (id)) {

return i;

}

}

}

return null;

}

/**

* @return the map

*/

public SortedMap<Container, List<Item>> getMapInstance () {

return map;

}

/**

* @return the map

*/

public SortedMap<Container, List<Item>> getMapClone (int index) {<Container, List<Item>> clone = new TreeMap<Container, List<Item>> (new MapKeysComparator (index));<Entry<Container, List<Item>>> set = map. entrySet ();

for (Entry<Container, List<Item>> e: set) {<Item> items = new ArrayList<Item> ();

for (Item i: e. getValue ()) {. add (i. clone ());

}. put (e. getKey (). clone (), items);

}

return clone;

}

/**

* @param map the map to set

*/

public void setMap (SortedMap<Container, List<Item>> map) {

this. map = map;

}

public boolean paretoSetIsEmpty () {

boolean result = false;

return result;

}

/**

* @return the rest

*/

public List<Item> getRest () {

return rest;

}

/**

* @param rest the rest to set

*/

public void setRest (List<Item> rest) {

this. rest = rest;

}

private void swap (int [] array, int index1, int index2) {

int temp=array [index1];[index1] = array [index2];[index2] = temp;

}

private void addSequence (List<List<Integer>> sequence, int [] array) {<Integer> subSequence = new ArrayList<Integer> ();

for (int i = 0; i < array. length; i++) {. add (new Integer (array [i]));

}. add (subSequence);

}

/**

*

* @param array - массив

* @param n - число переставляемых элементов

*/

private void permutations (List<List<Integer>> sequence, int [] array, int n) {

// Если нечего переставлять

if (n==1) {(sequence, array);

} else {

for (int i=0; i<n; i++) {(array, i,n-1); // меняем последний элемент с каждым,

// в том числе и с самим собой.(sequence, array,n-1); // запускаем функцию, для n-1 элементов(array, i,n-1); // поигрались - и хватит. Надо вернуть массив в прежнее

// состояние для следующего обмена элементов

}

}

}

/**

* @return the templates

*/

public List<List<Integer>> getTemplates () {

return templates;

}

}

Пакет util.. java

package util;

public class ContainerTemplate {

private IntegerDiapason volume;

private IntegerDiapason cargo;

public ContainerTemplate (IntegerDiapason volume, IntegerDiapason cargo) {

super ();

this. volume = volume;

this. cargo = cargo;

}

/**

* @return the volume

*/

public IntegerDiapason getVolume () {

return volume;

}

/**

* @return the cargo

*/

public IntegerDiapason getCargo () {

return cargo;

}

}. java

package util;

public class IntegerDiapason {

private int begin;

private int end;

public IntegerDiapason (int begin, int end) {

super ();

this. begin = begin;

this. end = end;

}

/**

* @return the begin

*/

public int getBegin () {

return begin;

}

/**

* @return the end

*/

public int getEnd () {

return end;

}

}. java

package util;

public class ItemTemplate {

private IntegerDiapason weight;

private IntegerDiapason volume;

private IntegerDiapason rate1;

private IntegerDiapason rate2;

private IntegerDiapason rate3;

private IntegerDiapason rate4;

private IntegerDiapason rate5;

public ItemTemplate (IntegerDiapason weight, IntegerDiapason volume,rate1, IntegerDiapason rate2,IntegerDiapason rate3, IntegerDiapason rate4, IntegerDiapason rate5) {

super ();

this. weight = weight;

this. volume = volume;

this. rate1 = rate1;

this. rate2 = rate2;

this. rate3 = rate3;

this. rate4 = rate4;

this. rate5 = rate5;

}

/**

* @return the weight

*/

public IntegerDiapason getWeight () {

return weight;

}

/**

* @return the volume

*/

public IntegerDiapason getVolume () {

return volume;

}

/**

* @return the rate1

*/

public IntegerDiapason getRate1 () {

return rate1;

}

/**

* @return the rate2

*/

public IntegerDiapason getRate2 () {

return rate2;

}

/**

* @return the rate3

*/

public IntegerDiapason getRate3 () {

return rate3;

}

/**

* @return the rate4

*/

public IntegerDiapason getRate4 () {

return rate4;

}

/**

* @return the rate5

*/

public IntegerDiapason getRate5 () {

return rate5;

}

}

Пакет gui.. java

package gui;

import javax. swing. JFrame;

import javax. swing. JTabbedPane;

import util. ContainerTemplate;

import util. ItemTemplate;

import core. Boss;

import core. Packer;

import core. Store;

/**

* Графический интерфейс.

* @author AtemB

*

*/

public class GUI {

private JFrame mainFrame;

private ObjectCreatorViewer oViewer;

private ParetoLayersViewer pViewer;

private ItemsViewer iViewer;

private ResultViewer rViewer;

private Store store;

public GUI (Store store, Packer packer, Boss boss, ContainerTemplate ct, ItemTemplate it) {

this. store = store;tabbedPane = new JTabbedPane ();= new ObjectCreatorViewer (this, this. store, ct, it, 40,8);= new ItemsViewer (store. getContainers (), store. getItemsInstance (), packer, boss);= new ParetoLayersViewer (this, store, packer);= new ResultViewer (this, store, packer, boss);

this. mainFrame = new JFrame ("Упаковка объектов");. addTab ("Задание исходных данных", oViewer. getViewer ());. addTab ("Объекты и контейнеры", iViewer. getViewer ());. addTab ("Слои Парето", pViewer. getViewer ());. addTab ("Результаты упаковки", rViewer. getViewer ());

this. mainFrame. setSize (1000, 550);

this. mainFrame. add (tabbedPane);

this. mainFrame. setDefaultCloseOperation (JFrame. EXIT_ON_CLOSE);

this. mainFrame. setVisible (true);

}

public void refreshItemsViewer () {. refreshTables (store. getContainers (), store. getItemsInstance ());

}

}. java

package gui;

import java. awt. GridBagConstraints;

import java. awt. GridBagLayout;

import java. awt. Insets;

import java. awt. event. ActionEvent;

import java. awt. event. ActionListener;

import java. awt. event. MouseWheelEvent;

import java. awt. event. MouseWheelListener;

import java. util. HashMap;

import java. util. Map;

import javax. swing. BorderFactory;

import javax. swing. JButton;

import javax. swing. JLabel;

import javax. swing. JPanel;

import javax. swing. JSpinner;

import javax. swing. SpinnerNumberModel;

import util. ContainerTemplate;

import util. ItemTemplate;

import core. Store;

class ObjectCreatorViewer {

private JPanel viewer;

private JPanel containersPanel;

private JSpinner containersNum;

private JSpinner cVolume;

private JSpinner cargo;

private JPanel itemsPanel;

private JSpinner itemsNum;

private JSpinner iVolume;

private JSpinner weight;

private JButton createButton;

private Store store;

private ContainerTemplate ct;

private ItemTemplate it;

private int topItemsNum;

private int topContainersNum;

private GUI gui;

private Map<JSpinner, Integer [] > spinnersTopValues;

public ObjectCreatorViewer (GUI gui, Store store,ct,it,

final int topItemsNum,

final int topContainersNum) {

this. gui = gui;

this. ct = ct;

this. it = it;

this. topItemsNum = topItemsNum;

this. topContainersNum = topContainersNum;

this. store = store;

this. spinnersTopValues = new HashMap<JSpinner, Integer [] > ();containersNumPanel = new JPanel ();= new JSpinner (new SpinnerNumberModel (1, 1, topContainersNum, 1));(containersNum);. put (containersNum, new Integer [] {1, topContainersNum});. add (new JLabel ("Количесвто контейнеров (1 - " + topContainersNum + "): "));. add (containersNum);cVolumePanel = new JPanel ();

int bottomContainerVolume = ct. getVolume (). getBegin ();

int topContainerVolume = ct. getVolume (). getEnd ();= new JSpinner (new SpinnerNumberModel (bottomContainerVolume, bottomContainerVolume, topContainerVolume, 1));(cVolume);. put (cVolume, new Integer [] {bottomContainerVolume, topContainerVolume});. add (new JLabel ("Объём одного контейнера, max (" + bottomContainerVolume + " - " + topContainerVolume +"): "));. add (cVolume);cargoPanel = new JPanel ();

int bottomCargo = ct. getCargo (). getBegin ();

int topCargo = ct. getCargo (). getEnd ();= new JSpinner (new SpinnerNumberModel (bottomCargo, bottomCargo, topCargo, 1));(cargo);. put (cargo, new Integer [] {bottomCargo, topCargo});. add (new JLabel ("Грузоподъёмность одного контейнера, max (" + bottomCargo + " - " + topCargo + "): "));. add (cargo);= new JPanel (new GridBagLayout ());. add (containersNumPanel, new GridBagConstraints (0, 0, 1, 1, 0, 0, GridBagConstraints. NORTHWEST,. BASELINE, new Insets (5, 5, 5,5), 0, 0));. add (cVolumePanel, new GridBagConstraints (0, 1, 1, 1, 0, 0, GridBagConstraints. NORTHWEST,. BASELINE, new Insets (5, 5, 5,5), 0, 0));. add (cargoPanel, new GridBagConstraints (0, 2, 1, 2, 0, 0, GridBagConstraints. NORTHWEST,. BASELINE, new Insets (5, 5, 5,5), 0, 0));. setBorder (BorderFactory. createTitledBorder ("Создание контейнеров"));itemsNumPanel = new JPanel ();= new JSpinner (new SpinnerNumberModel (1, 1, topItemsNum, 1));(itemsNum);. put (itemsNum, new Integer [] {1, topItemsNum});. add (new JLabel ("Количесвто объектов (1 - " + topItemsNum + "): "));. add (itemsNum);iVolumePanel = new JPanel ();

int singleItemBottomVolume = it. getVolume (). getBegin ();

int singleItemTopVolume = it. getVolume (). getEnd ();= new JSpinner (new SpinnerNumberModel (singleItemBottomVolume, singleItemBottomVolume, singleItemTopVolume, 1));(iVolume);. put (iVolume, new Integer [] {singleItemBottomVolume, singleItemTopVolume});. add (new JLabel ("Объём одного объекта, max (" + singleItemBottomVolume + " - " + singleItemTopVolume + "): "));. add (iVolume);weightPanel = new JPanel ();

int singleItemBottomWeight = it. getVolume (). getBegin ();

int singleItemTopWeight = it. getVolume (). getEnd ();= new JSpinner (new SpinnerNumberModel (singleItemBottomWeight, singleItemBottomWeight, singleItemTopWeight, 1));(weight);. put (weight, new Integer [] {singleItemBottomWeight, singleItemTopWeight});. add (new JLabel ("Вес одного объекта, max (" + singleItemBottomWeight + " - " + singleItemTopWeight + "): "));. add (weight);= new JPanel (new GridBagLayout ());. add (itemsNumPanel, new GridBagConstraints (0, 0, 1, 1, 0, 0, GridBagConstraints. NORTHWEST,. NONE, new Insets (5, 5, 5,5), 0, 0));. add (iVolumePanel, new GridBagConstraints (0, 1, 1, 1, 0, 0, GridBagConstraints. NORTHWEST,. NONE, new Insets (5, 5, 5,5), 0, 0));. add (weightPanel, new GridBagConstraints (0, 2, 1, 1, 0, 0, GridBagConstraints. NORTHWEST,. NONE, new Insets (5, 5, 5,5), 0, 0));. setBorder (BorderFactory. createTitledBorder ("Создание объектов"));= new JButton ("Создать");. addActionListener (new ActionListener () {

@Override

public void actionPerformed (ActionEvent arg0) {s = ObjectCreatorViewer. this. store;. setEmpty ();. createContainers (getSpinnerValue (containersNum), ObjectCreatorViewer. this. ct, getSpinnerValue (cVolume), getSpinnerValue (cargo));

// LayouterLauncher. printContainersSumParameters (s. getContainers ());. createItems (getSpinnerValue (itemsNum), ObjectCreatorViewer. this. it, getSpinnerValue (iVolume), getSpinnerValue (weight));

// LayouterLauncher. printItemsSumParameters (s. getItems ());. this. gui. refreshItemsViewer ();

}

});= new JPanel (new GridBagLayout ());. add (containersPanel, new GridBagConstraints (0, 0, 1, 1, 1, 1, GridBagConstraints. NORTHWEST, GridBagConstraints. VERTICAL, new Insets (5, 5, 5,5), 0, 0));. add (itemsPanel, new GridBagConstraints (1, 0, 1, 1, 1, 1, GridBagConstraints. NORTHEAST, GridBagConstraints. VERTICAL, new Insets (5, 5, 5,5), 0, 0));. add (createButton, new GridBagConstraints (1, 1, 1, 1, 0, 0, GridBagConstraints. SOUTHEAST, GridBagConstraints. NONE, new Insets (5, 5, 5,5), 0, 0));

}

/**

* @return the viewer

*/

public JPanel getViewer () {

return viewer;

}

private int getSpinnerValue (JSpinner s) {

return ( (SpinnerNumberModel) s. getModel ()). getNumber (). intValue ();

}

int getContainersNum () {

return getSpinnerValue (containersNum);

}

int getMaxContainerVolume () {

return getSpinnerValue (cVolume);

}

int getMaxCargo () {

return getSpinnerValue (cargo);

}

int getItemsNum () {

return getSpinnerValue (itemsNum);

}

int getMaxItemVolume () {

return getSpinnerValue (iVolume);

}

int getMaxWeight () {

return getSpinnerValue (weight);

}

/**

* @return the topItemsNum

*/

public int getTopItemsNum () {

return topItemsNum;

}

/**

* @return the topContainersNum

*/

public int getTopContainersNum () {

return topContainersNum;

}

private void addStandardWheelListener (final JSpinner spinner) {. addMouseWheelListener (new MouseWheelListener () {

@Override

public void mouseWheelMoved (MouseWheelEvent e) {

int bottom = values [0];

int top = values [1];

if (bottom <= value && value <= top) {

( (JSpinner) e. getComponent ()). setValue (value);

}

}

});

}

}. java

package gui;

import java. awt. GridBagConstraints;

import java. awt. GridBagLayout;

import java. awt. Insets;

import java. awt. event. ActionEvent;

import java. awt. event. ActionListener;

import java. awt. event. MouseAdapter;

import java. awt. event. MouseEvent;

import java. util. HashSet;

import java. util. List;

import java. util. Set;

import javax. swing. JButton;

import javax. swing. JLabel;

import javax. swing. JPanel;

import javax. swing. JScrollPane;

import javax. swing. JTable;

import javax. swing. event. TableModelEvent;

import javax. swing. event. TableModelListener;

import javax. swing. table. TableModel;

import javax. swing. table. TableRowSorter;

import core. Boss;

import core. Container;

import core. Item;

import core. Packer;

class ItemsViewer {

class ContainerTableModel implements TableModel {

private List<Container> containers;

private Set<TableModelListener> listeners = new HashSet<TableModelListener> ();

public ContainerTableModel (List<Container> containers) {

this. containers = containers;

}

@Override

public void addTableModelListener (TableModelListener columnIndex) {. add (columnIndex);

}

@Override

public Class<? > getColumnClass (int columnIndex) {

return Integer. class;

}

@Override

public int getColumnCount () {

return 3;

}

@Override

public String getColumnName (int columnIndex) {

switch (columnIndex) {

case 0:

return "ID";

case 1:

return "Объём";

case 2:

return "Грузоподъёмность";

}

return "column index error: \ngetted index = " + columnIndex + ",\nmost admissible index = " + (getColumnCount () - 1);

}

@Override

public int getRowCount () {

return containers. size ();

}

@Override

public Object getValueAt (int rowIndex, int columnIndex) {c = containers. get (rowIndex);

switch (columnIndex) {

case 0:

return c. getId ();

case 1:

return c. getVolume ();

case 2:

return c. getCargo ();

}

return null;

}

@Override

public boolean isCellEditable (int rowIndex, int columnIndex) {

switch (columnIndex) {

case 0:

return false;

case 1:

case 2:

return true;

}

return false;

}

@Override

public void removeTableModelListener (TableModelListener l) {. remove (l);

}

@Override

public void setValueAt (Object arg0, int rowIndex, int columnIndex) {c = containers. get (rowIndex);

switch (columnIndex) {

case 1:. setVolume ( (int) arg0);

break;

case 2:. setCargo ( (int) arg0);

break;

}

}

}

class ItemTableModel implements TableModel {

private List<Item> items;

private Set<TableModelListener> listeners = new HashSet<TableModelListener> ();

public ItemTableModel (List<Item> items) {

this. items = items;

}

@Override

public void addTableModelListener (TableModelListener l) {. add (l);

}

@Override

public Class<? > getColumnClass (int columnIndex) {

switch (columnIndex) {

case 0:

return Integer. class;

case 1:

return Integer. class;

case 2:

return Integer. class;

case 3:

return Integer. class;

case 4:

return Integer. class;

case 5:

return Integer. class;

case 6:

return Integer. class;

case 7:

return Integer. class;

case 8:

return Double. class;

case 9:

return String. class;

}

return null;

}

@Override

public int getColumnCount () {

return 10;

}

@Override

public String getColumnName (int columnIndex) {

switch (columnIndex) {

case 0:

return "ID";

case 1:

return "Объём";

case 2:

return "Вес";

case 3:

return "Кр.1";

case 4:

return "Кр.2";

case 5:

return "Кр.3";

case 6:

return "Кр.4";

case 7:

return "Кр.5";

case 8:

return "Полезность";

case 9:

return "Пара";

}

return "item index error: \ngetted index = " + columnIndex + ",\nmost admissible index = " + (getColumnCount () - 1);

}

@Override

public int getRowCount () {

return items. size ();

}

@Override

public Object getValueAt (int rowIndex, int columnIndex) {

switch (columnIndex) {

case 0:

return Integer. parseInt (items. get (rowIndex). getId ());

case 1:

return items. get (rowIndex). getVolume ();

case 2:

return items. get (rowIndex). getWeight ();

case 3:

return items. get (rowIndex). getRate1 ();

case 4:

return items. get (rowIndex). getRate2 ();

case 5:

return items. get (rowIndex). getRate3 ();

case 6:

return items. get (rowIndex). getRate4 ();

case 7:

return items. get (rowIndex). getRate5 ();

case 8:

return boss. getUtility (items. get (rowIndex));

case 9:

if (items. get (rowIndex). getPair ()! = null) {

return items. get (rowIndex). getPair (). getId ();

} else {

return null;

}

}

return null;

}

@Override

public boolean isCellEditable (int rowIndex, int columnIndex) {

if (columnIndex! = 0 && columnIndex! = 8 && columnIndex! = 9) {

return true;

}

return false;

}

@Override

public void removeTableModelListener (TableModelListener l) {. remove (l);

}

@Override

public void setValueAt (Object aValue, int rowIndex, int columnIndex) {i = items. get (rowIndex);

switch (columnIndex) {

case 1:. setVolume ( (Integer) aValue);

break;

case 2:. setWeight ( (Integer) aValue);

break;

case 3:. setRate1 ( (Integer) aValue);

break;

case 4:. setRate2 ( (Integer) aValue);

break;

case 5:. setRate3 ( (Integer) aValue);

break;

case 6:. setRate4 ( (Integer) aValue);

break;

case 7:. setRate5 ( (Integer) aValue);

break;

}

}

public void recountUtilities () {

for (int i = 0; i < items. size (); i++) {(ItemsViewer. this. boss. getUtility (items. get (i)), i,

);

}

}getElement (int index) {

return items. get (index);

}<Item> getElements () {

return items;

}

}

private JPanel viewer;

private JTable itemTable;

private JTable containersTable;

private JButton createPairButton;

private JButton breakPairButton;

private JLabel pairsNum;

private JLabel pairsCount;

private Packer packer;

private Boss boss;

public ItemsViewer (List<Container> containers, List<Item> items, Packer packer, Boss boss) {

this. boss = boss;

this. packer = packer;= new JPanel (new GridBagLayout ());itm = new ItemTableModel (items);. addTableModelListener (new TableModelListener () {

@Override

public void tableChanged (TableModelEvent e) {

( (ItemTableModel) e. getSource ()). recountUtilities ();

}

});= new JTable (itm);<ItemTableModel> sorter = new TableRowSorter<ItemTableModel> ( (ItemTableModel) itemTable. getModel ());. setSortable (9, false);. setRowSorter (sorter);. addMouseListener (new MouseAdapter () {

@Override

public void mouseReleased (MouseEvent arg0) {

int [] selectedRowIndices = ( (JTable) arg0. getComponent ()). getSelectedRows ();

if (selectedRowIndices. length == 2) {. setEnabled (false);

boolean single = true;

for (int index: selectedRowIndices) {= ( (JTable) arg0. getComponent ()). getModel (). getValueAt (index,

) == null;

if (! single) {. setEnabled (false);

break;

}

}

if (single) {. setEnabled (true);

}

} else if (selectedRowIndices. length == 1) {. setEnabled (false);

if ( ( (ItemTableModel) itemTable. getModel ()). getElement (selectedRowIndices [0]). hasPair ()) {. setEnabled (true);

} else {. setEnabled (false);

}

} else {. setEnabled (false);. setEnabled (false);

}

}

});= new JTable (new ContainerTableModel (containers));. setRowSorter (new TableRowSorter<ContainerTableModel> ( (ContainerTableModel) containersTable. getModel ()));= new JButton ("Создать пару");. addActionListener (new ActionListener () {

@Override

public void actionPerformed (ActionEvent e) {

int [] selectedRowIndices = itemTable. getSelectedRows ();i1 = ( (ItemTableModel) itemTable. getModel ()). getElement (selectedRowIndices [0]);i2 = ( (ItemTableModel) itemTable. getModel ()). getElement (selectedRowIndices [1]);. this. packer. createPair (i1, i2);. setText (ItemsViewer. this. packer. countPairs ( ( (ItemTableModel) itemTable. getModel ()). getElements ()) + "");. repaint ();

( (JButton) e. getSource ()). setEnabled (false);

}

});. setEnabled (false);= new JButton ("Разбить пару");. addMouseListener (new MouseAdapter () {

@Override

public void mousePressed (MouseEvent e) {i1 = ( (ItemTableModel) itemTable. getModel ()). getElement (itemTable. getSelectedRows () [0]);i2 = i1. getPair ();. this. packer. breakPair (i1, i2);. repaint ();

( (JButton) e. getSource ()). setEnabled (false);. setText (ItemsViewer. this. packer. countPairs ( ( (ItemTableModel) itemTable. getModel ()). getElements ()) + "");

}

});. setEnabled (false);= new JLabel ("Количество пар: ");= new JLabel (packer. countPairs ( ( (ItemTableModel) itemTable. getModel ()). getElements ()) + "");buttons = new JPanel ();. add (createPairButton);. add (breakPairButton);labels = new JPanel ();. add (pairsNum);. add (pairsCount);. add (new JScrollPane (itemTable), new GridBagConstraints (0, 0, 1, 1, 1, 1, GridBagConstraints. NORTHWEST, GridBagConstraints. VERTICAL, new Insets (5, 5, 5,5), 0, 0));. add (new JScrollPane (containersTable), new GridBagConstraints (1, 0, 1, 1, 1, 1, GridBagConstraints. NORTHWEST, GridBagConstraints. VERTICAL, new Insets (5, 5, 5,5), 0, 0));. add (buttons, new GridBagConstraints (0, 2, 1, 1, 1, 0, GridBagConstraints. SOUTHWEST, GridBagConstraints. NONE, new Insets (5, 5, 5,5), 0, 0));. add (labels, new GridBagConstraints (1, 2, 1, 1, 1, 0, GridBagConstraints. SOUTHWEST, GridBagConstraints. NONE, new Insets (5, 5, 5,5), 0, 0));

}

public void refreshTables (List<Container> containers, List<Item> items) {. setModel (new ItemTableModel (items));. setModel (new ContainerTableModel (containers));

}

/**

* @return the viewer

*/

public JPanel getViewer () {

return viewer;

}

}. java

package gui;

import java. awt. GridBagConstraints;

import java. awt. GridBagLayout;

import java. awt. Insets;

import java. awt. event. ActionEvent;

import java. awt. event. ActionListener;

import java. util. HashSet;

import java. util. List;

import java. util. Set;

import javax. swing. JButton;

import javax. swing. JCheckBox;

import javax. swing. JPanel;

import javax. swing. JScrollPane;

import javax. swing. JTable;

import javax. swing. event. TableModelListener;

import javax. swing. table. TableColumn;

import javax. swing. table. TableModel;

import core. Item;

import core. Packer;

import core. Store;

class ParetoLayersViewer {

class ParetoLayersTableModel implements TableModel {

private List<List<Item>> paretoLayers;

private Set<TableModelListener> listeners = new HashSet<TableModelListener> ();

public ParetoLayersTableModel (List<List<Item>> paretoLayers) {

super ();

this. paretoLayers = paretoLayers;

}

@Override

public void addTableModelListener (TableModelListener l) {. add (l);

}

@Override

public Class<? > getColumnClass (int columnIndex) {

return String. class;

}

@Override

public int getColumnCount () {

int maxLayerSize = 0;

for (List<Item> l: paretoLayers) {

int currentLayerSize = l. size ();

if (maxLayerSize < currentLayerSize) {= currentLayerSize;

}

}

return maxLayerSize;

}

@Override

public String getColumnName (int columnIndex) {

return (columnIndex + 1) + "";

}

@Override

return paretoLayers. size ();

}

@Override

public Object getValueAt (int rowIndex, int columnIndex) {<Item> paretoLayer = paretoLayers. get (rowIndex);

if (paretoLayer. size () > columnIndex) {

return paretoLayer. get (columnIndex). getId ();

}

return null;

}

@Override

public boolean isCellEditable (int rowIndex, int columnIndex) {

return false;

}

@Override

public void removeTableModelListener (TableModelListener l) {. remove (l);

}

@Override

public void setValueAt (Object aValue, int rowIndex, int columnIndex) {

}

}

private JPanel viewer;

private JTable paretoLayersTable;

private JCheckBox byUtilityBox;

private JCheckBox byVolumeBox;

private JCheckBox byWeightBox;

private JCheckBox processPairsBox;

private JButton recountButton;

private Store store;

private Packer packer;

public ParetoLayersViewer (GUI gui, Store store, Packer packer) {

this. store = store;

this. packer = packer;

this. viewer = new JPanel (new GridBagLayout ());

this. byUtilityBox = new JCheckBox ("По полезности", false);. addActionListener (new ActionListener () {

@Override

public void actionPerformed (ActionEvent arg0) {();

}

});

this. byVolumeBox = new JCheckBox ("По объёму", false);

this. byWeightBox = new JCheckBox ("По весу", false);

this. recountButton = new JButton ("Пересчитать");. addActionListener (new ActionListener () {

@Override

public void actionPerformed (ActionEvent e) {(ParetoLayersViewer. this. store. getItemsClones ());

}

});= new JCheckBox ("Обрабатывать парные объекты", true);checkBoxesPanel = new JPanel ();. add (byVolumeBox);. add (byWeightBox);. add (byUtilityBox);. add (processPairsBox);. add (recountButton);= new JTable ();. add (new JScrollPane (paretoLayersTable), new GridBagConstraints (0, 0, 1, 1, 1, 1, GridBagConstraints. NORTHWEST, GridBagConstraints. BOTH, new Insets (5, 5, 0, 0), 0, 0));. add (checkBoxesPanel, new GridBagConstraints (0, 1, 1, 1, 1, 1, GridBagConstraints. SOUTHWEST, GridBagConstraints. NONE, new Insets (5, 0, 5, 0), 0, 0));();

}

public void recountLayers (List<Item> sourceSet) {

if (processPairsBox. isSelected ()) {= packer. processPairs (sourceSet);

}<List<Item>> paretoSet = packer. createParetoSet (sourceSet);

if (byUtilityBox. isSelected ()) {

for (List<Item> paretoLayer: paretoSet) {. sort (paretoLayer, Packer. SORT_TYPE. UTILITY);

}

} else {

if (byVolumeBox. isSelected () && byWeightBox. isSelected ()) {

for (List<Item> paretoLayer: paretoSet) {. sort (paretoLayer, Packer. SORT_TYPE. VOLUME, Packer. SORT_TYPE. WEIGHT);

}

} else {

if (byVolumeBox. isSelected ()) {

for (List<Item> paretoLayer: paretoSet) {. sort (paretoLayer, Packer. SORT_TYPE. VOLUME);

}

} else if (byWeightBox. isSelected ()) {

for (List<Item> paretoLayer: paretoSet) {. sort (paretoLayer, Packer. SORT_TYPE. WEIGHT);

}

}

}

}. setParetoSet (paretoSet);. setModel (new ParetoLayersTableModel (paretoSet));

for (int i = 0; i < paretoLayersTable. getColumnCount (); i++) {column = paretoLayersTable. getColumn ( (i + 1) + "");. setMinWidth (35);

}

}

/**

* @return the paretoLayersPanel

*/

public JPanel getViewer () {

return viewer;

}

private void refreshBoxes () {

boolean state =! byUtilityBox. isSelected ();. setEnabled (state);. setEnabled (state);

}

}. java

package gui;

import java. awt.component;

import java. awt. GridBagConstraints;

import java. awt. GridBagLayout;

import java. awt. Insets;

import java. awt. event. ActionEvent;

import java. awt. event. ActionListener;

import java. awt. event. ItemEvent;

import java. awt. event. ItemListener;

import java. text. DecimalFormat;

import java. text. DecimalFormatSymbols;

import java. util. ArrayList;

import java. util. HashSet;

import java. util. Hashtable;

import java. util. List;

import java. util. Set;

import java. util. SortedMap;

import javax. swing.comboBoxModel;

import javax. swing. ImageIcon;

import javax. swing. JButton;

import javax. swing. JComboBox;

import javax. swing. JLabel;

import javax. swing. JPanel;

import javax. swing. JScrollPane;

import javax. swing. JSplitPane;

import javax. swing. JTextPane;

import javax. swing. JTree;

import javax. swing. event. ListDataListener;

import javax. swing. tree. DefaultMutableTreeNode;

import javax. swing. tree. DefaultTreeCellRenderer;

import javax. swing. tree. DefaultTreeModel;

import javax. swing. tree. TreeCellRenderer;

import javax. swing. tree. TreePath;

import core. Boss;

import core. Container;

import core. Item;

import core. Packer;

import core. Store;

import core. Packer. ALGORYTHM;

class ResultViewer {

private class Resume {

private String algNameReport;

private String effectivityReport;

private String restReport;

private String packedReport;

private DecimalFormat format;

public Resume () {f = new DecimalFormatSymbols ();. setDecimalSeparator ('. ');= new DecimalFormat ("#,##0.00", f);

}

/**

* @param algNameReport the algNameReport to set

*/

public void setAlgNameReport (String algNameReport) {

this. algNameReport = "<h2><font color='RED'>Алгоритм: " + algNameReport + "</text></h2><p>";

}

/**

* @param effectivityReport the effectivityReport to set

*/

public void setEffectivityReport (SortedMap<Container, List<Item>> map) {header = "<h3><font color='RED'>Эффективность алгоритма</font></h3>";

double occupiedSpacePercent = 0;

double loadPercent = 0;

double volumeAccumulator = 0;

double weightAccumulator = 0;

double iVolumeAccumulator = 0;

double cargoAccumulator = 0;

for (Container c: map. keySet ()) {

for (Item i: map. get (c)) {+= i. getVolume ();+= i. getWeight ();

}+= c. getVolume ();+= c. getCargo ();

}= (iVolumeAccumulator / volumeAccumulator) * 100;= (weightAccumulator / cargoAccumulator) * 100;occupiedSpacePercentString = getFormattedPair ("Процент заполнения пространства контейнеров", occupiedSpacePercent);loadPercentString = getFormattedPair ("Процент загрузки контейнеров", loadPercent);loadedItemsMass = getFormattedPair ("Общая масса упакованных объектов", weightAccumulator);loadedItemsVolume = getFormattedPair ("Общий объём упакованных объектов", iVolumeAccumulator);effectivityReport = occupiedSpacePercentString + loadPercentString + loadedItemsVolume + loadedItemsMass;

this. effectivityReport = header + effectivityReport;

}

/**

* @param restReport the restReport to set

*/

public void setRestReport (Store store) {header = "<h3><font color='RED'>Остаток на складе</font></h3>";

double volumeAccumulator = 0;

double weightAccumulator = 0;

for (Item i: store. getRest ()) {+= i. getVolume ();+= i. getWeight ();

}restVolume = getFormattedPair ("Общий объём оставшихся объектов", volumeAccumulator);restWeight = getFormattedPair ("Общий вес оставшихся объектов", weightAccumulator);

this. restReport = header + restVolume + restWeight;

}

/**

* @param packedReport the packedReport to set

*/

public void setPackedReport (SortedMap<Container, List<Item>> map) {packedReport = "<h3><font color='RED'>Упакованные объекты</font></h3>";

for (Container c: map. keySet ()) {containerID = "Контейнер ";itemsID = "Объекты: ";freeSpace = "Свободное место в контейнере: ";freeCargo = "Неиспользованная грузоподъёмность: ";

double iVolumeAccumulator = 0;

double iWeightAccumulator = 0;+= c. getId () + "<br>";

for (Item i: map. get (c)) {+= " " + i. getId ();+= i. getVolume ();+= i. getWeight ();

}+= "<br>";+= (c. getVolume () - iVolumeAccumulator) + "<br>";+= (c. getCargo () - iWeightAccumulator) + "<br>";+= containerID + itemsID + freeSpace + freeCargo + "<br>";

}

this. packedReport = packedReport;

}

/**

* @return the algNameReport

*/

public String getAlgNameReport () {

return algNameReport;

}

/**

* @return the effectivityReport

*/

public String getEffectivityReport () {

return effectivityReport;

}

/**

* @return the restReport

*/

public String getRestReport () {

return restReport;

}

/**

* @return the packedReport

*/

public String getPackedReport () {

return packedReport;

}

private String getFormattedPair (String string, double value) {

return "<font color='BLUE'>" + string + ": " +

"<font color='GREEN'><b>" + format. format (value) + "</b></font></font><br>";

}

}

private class ConsoleLogTextPane extends JTextPane {

/**

*

*/

private static final long serialVersionUID = - 5691372469851601341L;

private String TEMPLATE = "<html><title></title><body></body></html>";

private String buffer;

private int breakIndex;

public ConsoleLogTextPane () {(TEMPLATE);("text/html");= 0;

}

public void addString (String str) {= this. getText ();= buffer. lastIndexOf ("</body>");= buffer. substring (0, breakIndex) + str + buffer. substring (breakIndex);

this. setText (buffer);

}

public void clearConsole () {

this. setText (TEMPLATE);

}

}

class AlgorythmsComboBoxModel implements ComboBoxModel<String> {

private Set<ListDataListener> listeners;

private List<String> elements;

private String selected;

public AlgorythmsComboBoxModel (String. strings) {= new HashSet<ListDataListener> ();= new ArrayList<String> ();= "";

for (String s: strings) {. add (s);

}

}

@Override

public void addListDataListener (ListDataListener l) {. add (l);

}

@Override

public String getElementAt (int index) {

return elements. get (index);

}

@Override

public int getSize () {

return elements. size ();

}

@Override

public void removeListDataListener (ListDataListener l) {. remove (l);

}

@Override

public Object getSelectedItem () {

return selected;

}

@Override

public void setSelectedItem (Object anItem) {= (String) anItem;

}

}

class ResultTreeCellRenderer implements TreeCellRenderer {

private JLabel label = new JLabel ();

@Override

public Component getTreeCellRendererComponent (JTree tree, Object value,

boolean selected, boolean expanded, boolean leaf, int row,

boolean hasFocus) {

if ( (value! = null) && (value instanceof DefaultMutableTreeNode)) {icon = null;node = (DefaultMutableTreeNode) value;userObject = node. getUserObject ();

if (userObject instanceof Container) {= new ImageIcon (ResultViewer. class. getResource ("images/Container. png"));. setText ("Контейнер, ID: " + ( (Container) userObject). getId ());

} else if (userObject instanceof Item) {= new ImageIcon (ResultViewer. class. getResource ("images/Item. png"));. setText ("Объект, ID: " + ( (Item) userObject). getId ());

} else if (userObject instanceof String) {

if (node. getParent () == null ||. getParent () == value) {= new ImageIcon (ResultViewer. class. getResource ("images/Containers. png"));

} else {= new ImageIcon (ResultViewer. class. getResource ("images/Field. png"));

}. setText ( (String) node. getUserObject ());

}. setOpaque (true);

if (selected) {. setBackground (new DefaultTreeCellRenderer (). getBackgroundSelectionColor ());

} else {. setBackground (new DefaultTreeCellRenderer (). getBackgroundNonSelectionColor ());

}. setIcon (icon);

}

return label;

}

}

private JPanel viewer;

private JTree tree;

private JPanel treePanel;

private JPanel cBoxPanel;

private JButton packButton;

private JButton clearConsoleButton;

private ConsoleLogTextPane resumeLoggerPane;

private JSplitPane splitPane;

private JComboBox<String> algorythmsBox;

private Hashtable<String, Packer. ALGORYTHM> table;

private final String NO_ALGORYTHM_CHOSEN = "Выберите алгоритм";

private final String FIRST = "В первый подходящий";

private final String BEST = "В лучший из подходящих";

private Resume resume;

public ResultViewer (final GUI gui, final Store store, final Packer packer, final Boss boss) {= new ConsoleLogTextPane ();. setEditable (false);= new Resume ();top = new DefaultMutableTreeNode (" [пусто] ");= new Hashtable<String, Packer. ALGORYTHM> ();. put (FIRST, ALGORYTHM. FIRST);. put (BEST, ALGORYTHM. BEST);= new JComboBox<String> (new AlgorythmsComboBoxModel (NO_ALGORYTHM_CHOSEN, FIRST, BEST));. setSelectedIndex (0);. addItemListener (new ItemListener () {

@SuppressWarnings ("unchecked")

@Override

public void itemStateChanged (ItemEvent arg0) {. setEnabled ( ( (JComboBox<String>) arg0. getSource ()). getModel (). getSelectedItem ()! = NO_ALGORYTHM_CHOSEN &&. getParetoSetInstance ()! = null &&

! store. getParetoSetInstance (). isEmpty ());

}

});= new JButton ("Упаковать");. setEnabled (false);. addActionListener (new ActionListener () {

@Override

public void actionPerformed (ActionEvent arg0) {

if (store! = null) {. getRest (). clear ();

if (store. getParetoSetInstance ()! = null) {<List<Integer>> templates = store. getTemplates ();

double maxUtilityRate = 0;

int maxUtilityIndex = 0;<Container, List<Item>> map = null;

for (int i = 0; i < templates. size (); i++) {= store. getMapClone (i);

for (List<Item> paretoLayer: store. getParetoSetClone ()) {. pack (map, paretoLayer, table. get (algorythmsBox. getSelectedItem ()));

}

double utilityRate = boss. getPackUtility (map);

if (maxUtilityRate < utilityRate) {= utilityRate;= i;

}. getRest (). clear ();

}= store. getMapClone (maxUtilityIndex);

for (List<Item> paretoLayer: store. getParetoSetClone ()) {. pack (map, paretoLayer, table. get (algorythmsBox. getSelectedItem ()));

}(map); resume. setAlgNameReport ( (String) ResultViewer. this. algorythmsBox. getSelectedItem ());. setEffectivityReport (map);. setRestReport (store);. setPackedReport (map);. addString (resume. getAlgNameReport ());. addString (resume. getEffectivityReport ());. addString (resume. getRestReport ());. addString (resume. getPackedReport ());

}

}

}

});= new JButton ("Очистить");. addActionListener (new ActionListener () {

@Override

public void actionPerformed (ActionEvent arg0) {. this. resumeLoggerPane. clearConsole ();

}

});= new JPanel (new GridBagLayout ());= new JTree (top);. setCellRenderer (new ResultTreeCellRenderer ());= new JPanel (new GridBagLayout ());. add (new JScrollPane (tree), new GridBagConstraints (0, 0, 1, 1, 1, 1, GridBagConstraints. NORTHWEST, GridBagConstraints. BOTH, new Insets (0, 0, 0, 0), 0, 0));= new JPanel (new GridBagLayout ());= new JSplitPane (JSplitPane. HORIZONTAL_SPLIT, treePanel, cBoxPanel);. setOneTouchExpandable (true);. setDividerLocation (350);. add (new JScrollPane (resumeLoggerPane), new GridBagConstraints (0, 0, 2, 1, 1, 1, GridBagConstraints. NORTHEAST, GridBagConstraints. BOTH, new Insets (0, 0, 0, 0), 0, 0));. add (algorythmsBox, new GridBagConstraints (0, 1, 1, 1, 0, 0, GridBagConstraints. NORTHEAST, GridBagConstraints. NONE, new Insets (0, 0, 0, 0), 0, 0));. add (packButton, new GridBagConstraints (1, 1, 1, 1, 0, 0, GridBagConstraints. NORTHWEST, GridBagConstraints. NONE, new Insets (0, 0, 0, 0), 0, 0));. add (clearConsoleButton, new GridBagConstraints (1, 1, 1, 1, 0, 0, GridBagConstraints. NORTHEAST, GridBagConstraints. NONE, new Insets (0, 0, 0, 0), 0, 0));. add (splitPane, new GridBagConstraints (0, 0, 1, 1, 1, 1, GridBagConstraints. NORTHWEST, GridBagConstraints. BOTH, new Insets (5, 5, 5,5), 0, 0));

}

public void refreshTree (SortedMap<Container, List<Item>> map) {root = new DefaultMutableTreeNode ("Упакованные объекты", true);(root, map);

}

private void createTree (DefaultMutableTreeNode root, SortedMap<Container, List<Item>> map) {

( (DefaultMutableTreeNode) ( (DefaultTreeModel) tree. getModel ()). getRoot ()). removeAllChildren ();

( (DefaultTreeModel) tree. getModel ()). setRoot (root);container = null;item = null;containerField = null;itemField = null;<Container> containers = map. keySet ();

for (Container c: containers) {= new DefaultMutableTreeNode (c, true);<Item> items = map. get (c);= new DefaultMutableTreeNode ("ID: " + c. getId (), false);. add (containerField);= new DefaultMutableTreeNode ("Объём: " + c. getVolume (), false);. add (containerField);= new DefaultMutableTreeNode ("Грузоподъёмность: " + c. getCargo (), false);. add (containerField);

for (Item i: items) {= new DefaultMutableTreeNode (i, true);= new DefaultMutableTreeNode ("ID: " + i. getId (), false);. add (itemField);= new DefaultMutableTreeNode ("Объём: " + i. getVolume (), false);. add (itemField);= new DefaultMutableTreeNode ("Вес: " + i. getWeight (), false);. add (itemField);= new DefaultMutableTreeNode ("Кр.1: " + i. getRate1 (), false);. add (itemField);= new DefaultMutableTreeNode ("Кр.2: " + i. getRate2 (), false);. add (itemField);= new DefaultMutableTreeNode ("Кр.3: " + i. getRate3 (), false);. add (itemField);= new DefaultMutableTreeNode ("Кр.4: " + i. getRate4 (), false);. add (itemField);= new DefaultMutableTreeNode ("Кр.5: " + i. getRate5 (), false);. add (itemField);

if (i. hasPair ()) {= new DefaultMutableTreeNode ("ID парного объекта: " + i. getPair (). getId ());. add (itemField);

}. add (item);

}. add (container);

}. expandPath (new TreePath ( ( (DefaultMutableTreeNode) ( (DefaultMutableTreeNode) root. getChildAt (0)). getChildAt (3)). getPath ()));

}

/**

* @return the viewer

*/

public JPanel getViewer () {

return viewer;

}

}

Пакет launcher.. java

package launcher;

import gui. GUI;

import util. ContainerTemplate;

import util. IntegerDiapason;

import util. ItemTemplate;

import core. Boss;

import core. Packer;

import core. Store;

public class LayouterLauncher {

/**

* @param args

*/

public static void main (String [] args) {

// Задаём ограничения на предельные значения параметров объектов и контейнеров.ct = new ContainerTemplate (new IntegerDiapason (25, 40), new IntegerDiapason (25, 40));it = new ItemTemplate (new IntegerDiapason (1, 20),

new IntegerDiapason (1, 20),

new IntegerDiapason (1,5),

new IntegerDiapason (1,5),

new IntegerDiapason (1,5),

new IntegerDiapason (1,5)

);

// Создаём склад.store = new Store ();

// Создаём ЛПРboss = new Boss ();

// Создаём упаковщика.packer = new Packer (store, boss);

new GUI (store, packer, boss, ct, it);

}

}