вих контейнерів.
Але частина предметів з L3 можна укласти в контейнери для L2. Кожен з них
має 1 - wi, i? L2 вільного місця, де поміститься предметів з L3.
Слідство 1. Величина H=max {H1 (?), H2 (?), 0?? ? 0,5} є нижньою оцінкою для OPT (L).
Слідство 2.
Доказ. При? =0 отримуємо H? H1 (0)=max {| L2 |, H0}? H0.
Як знайти H, що не перебираючи всі значення? ?
Слідство 3. Нехай V - безліч всіх різних значень wi? 0,5.
Тоді
т. е. після сортування предметів отримуємо TH=O (n + nlog n).
2. Загальний алгоритм вирішення задачі про пакування
1. Попереднє упорядкування об'єктів відповідно до ставленням домінування.
Дослідження співвідношень за якістю об'єктів. Шляхом попарного порівняння об'єктів визначається асиметричне Транзитивне ставлення домінування:
P0={(yi, yj)? Y? Y |" k=1, ..., N; yik? Yjk і $ p: yip
. Виділення паретових шарів.
Відповідно до ставленням P0 на безлічі об'єктів можна виділити підмножина недомініруемих об'єктів. Після їх видалення можна виділити другу підмножина і т.д. до вичерпання безлічі. Виділені шару є паретовимі шарами.
. Попередня упаковка об'єктів.
Вона полягає в застосуванні алгоритму АОЧ по шарах.
Нехай упаковка об'єктів (i - 1) перший шарів можлива, але об'єкти i-го шару вже не входять. Розглянемо окремий випадок, коли кожен об'єкт (i - 1)-го шару перевершує кожен об'єкт i-го шару і кожен об'єкт i-го шару в свою чергу перевершує кожен об'єкт (i +1)-го шару, причому об'єкти, що належать одному шару , еквіваленти за якістю. У цьому випадку можна відразу переходити до кроку 6, т.к. є вся необхідна інформація для упаковки об'єктів в місці їх передбачуваного «розрізу» на групи упакованих та не упакованих об'єктів.
У загальному випадку така інформація відсутня. Для зменшення невизначеності потрібні кроки 4,5.
. Визначення інформації, що вимагається для попереднього упорядкування об'єктів.
Проводиться порівняння об'єктів (i - 1), i і (i +1) шарів, тобто тих шарів, де ймовірно відбудеться розподіл об'єктів при упаковці. Визначається обсяг інформації, необхідний для впорядкування цих об'єктів за якістю.
Якщо об'єкти цих шарів перебувають у відношенні домінування або «майже» домінування (тобто домінування за всіма критеріями, крім одного), то інформація для впорядкування цих об'єктів може бути отримана від ОПР шляхом прямого опитування. ЛПР пред'являють об'єкти (попарно) і з'ясовують, який з них для ЛПР є більш цінним. При виникненні протиріч (A> B> C> A) необхідно вказувати на ці протиріччя ЛПР для їх вирішення.
У загальному випадку об'єкти відрізняються оцінками за кількома критеріями і при цьому є досить представницькими елементами множини Y. Для їх упорядкування потрібна додаткова інформація про уподобання ЛПР.
Наприклад, якщо всі об'єкти можна розташувати відповідно до оцінок так, як це наведено ...
