3.2. Завдання про ранець

Нагадаємо лінійну булеву задачу про ранець, постановка якої наведена в Главі 1. Задано ємність ранцяB>0 і безліч предметівN=, кожен з якихJÎNмає “ цінність”CjІ “вага”Aj³0. Потрібно вибрати підмножину предметів максимальної сумарної цінності, загальна вага яких не перевищує ємності ранцяB. Вводячи змінніXj=1, якщо предметJÎNкладеться в ранець іXj=0 в іншому випадку, запишемо математичну модель проблеми:

Z=

Sk(L)=

Очевидно, оптимальне значення цільової функції вихідної задачі (3.2)-(3.3) дорівнюєZ=SN(b). Зауважимо також, що

  • якщо =0, тоSK(L)=SK-1(L);
  • якщо =1, тоSK(L)=Ck+SK-1(L-Ak).

Звідси випливають рекурентні співвідношення:

.

МаємоS1(L)=0 при0£L1, то вважаємоK=K-1 ,L=L-AnІ повторюємо ітерацію.

Як видно, оптимальне рішення NP-важкої булевої задачі про ранець будується алгоритмом ДП з трудомісткістюПсевдополіноміальноїO(nb).

Розберемо

Приклад 3.3.Розв'язати задачу

Скористаємося співвідношеннями (3.4) і заповнимо Табіцю 3.1, у кожній клітині(L,SK(L))Якій, поряд зі значеннямSK(L), будемо запам'ятовувати умовно-оптимальні рішенняXk(L)(після символу “/”).

В результаті прямого ходу знайдено оптимальне значення цільової функціїS4(7)=34 та останньої компоненти вектора-рішенняX4(7)=1. Отже, =1. ВважаємоK=3,L=L-A4= 7 - 5 = 2. РядокL=2 і стовпецьS2(2)Таб. 3.1 дозволяють знайти =0. Отже, вважаємоK=2,L=L-A3= 2 - 0 = 2. З таблиці видно також, що =0, а =1.

У Таб. 3.1 затемнені клітини, що дозволили відновити оптимальне рішення задачі.

завдання
Таб. 3.1.

Нехай тепер змінні завдання про ранець набувають цілих невід'ємних значень. Завдання перепишеться у вигляді

Z=

S(A)=

Теорема 3.1. Для задачі (3.5)-(3.6) справедливі рекурентні співвідношення:

S(A) =-ak) + ck>, 0£A£A .

(Максимум по порожньому безлічі вважаємо рівним нулю.)

Доказ. НехайX * (A)- оптимальний вектор. ТодіS(A) = (C,X*(A)). ЯкщоS(A)>0, то існує такий номерK, щоX(A)>0і(C,X*(A)) = (C,X*(A)-Ek) +Ck, деEk-K-й орт. Значить

S(A)£S(A-Ak) +Ck£-Ak) +Ck>.

З іншого боку

-ak) + ck>= S(A-ai) + ci = (c, x*(A-ai)) + ci =

Співвідношення (3.7) дозволяють визначити оптимальне значення функціоналу (3.5). Оптимальне рішення знаходиться за такою процедурою.

Зворотний хід.ПокладемоX*=0,A*=А. Потім послідовно розв'язуємо рівняння:

Щодо індексуK.

ЯкщоI– рішення рівняння (3.8), то вважаємоX=X+1;A*=A*-Aiі повторюємо ітерацію. Якщо рівняння (3.8) немає рішення, тоді векторX*оптимальний.

Відносини (3.7) у разі цілісних вагAkдозволяють вирішити завдання (3.5)-(3.6) з псевдополіноміальною трудомісткістю -O(An)І пам'яттю -O(A+ N).

Із завданням (3.5)-(3.6) тісно пов'язане, так зване, зворотне завдання:

Як і раніше, зануримо останнє завдання до сімействаB=0,1,…,B>, де завдання((B)):

Q(B)=

НехайX0(B)– оптимальне рішення задачі((B)).

Доказ. НехайB2>B1. Очевидно,X0(B2)- допустиме рішення задачі((B1)). Отже,Q(B2)=(A,X0(B2))³Q(B1).

Для зворотного завдання справедливі рекурентні співвідношення:

Q(0) = 0;Q(B) =MaxB-Ck>) +Ak>, 0£B£B,

Завдяки яким оптимальне рішення будується з трудомісткістю -O(NB)та пам'яттю -O(B+N).

Теорема 3.2. (зв'язок прямої та зворотної завдань про ранце). Нехай=MaxQ(B)£A,B³0>. ТодіS(A)=і оптимальне рішенняX0()зворотного завдання(())є оптимальним і для прямої задачі(P(A) ).

Доказ. ПозначимоS*=S(A). ОскількиX*(A)– допустимий вектор для обох завдань((S*))та(P(A)), тоQ (S*)(A,X*(A))£A. З нерівностіQ(S*)£Aі визначення випливає, що³S*. З іншого боку, оскільки оптимальне рішенняX0()зворотної задачі(())Є допустимим для прямої задачі(P(A))(оскільки(A,X0()) =Q()£A), то(C ,X0())£(C,X*(A)) =S*. Отже,=S*=S(A)та(C,X0() ) =S(A).

Слідство 3.1.У разі ціліснихCkтадовільнихAkдля вирішення прямої задачі про ранець можна використовувати алгоритм ДП, що має трудомісткістьO(NS*)і пам'ятьO(S*+N), деS*=S(A)£ACk.

Доказ. З Леми 3.1 і Теореми 3.2 випливає, що