Вметнување кутии

Денеска ќе разгледаме еден едноставен, но интересен проблем. Имаме N кутии и за секоја од нив ни се познати димензиите, односно висината, широчината и должината. Она што треба да го одредиме, е максималниот број на кутии кои може да се стават една во друга. Една кутија може да се стави во друга доколку за фиксна поставеност на втората кутија, постои просторна ротација на првата така што нејзините димензии се стриктно помали од соодветните димензии на втората. Понатаму во текстот, една кутија ќе ја претставувам со подредена тројка (x, y, z) каде x, y и z се нејзините димензии. На пример, кутијата (1, 4, 5) може да  се стави во кутијата (6, 3, 5) бидејќи може да се најде пермутација на димензиите на првата, имено (5, 1, 4) така што 5<6, 1<3 и 4<5. 

Понатаму во текстот, со пакет ќе означуваме множество од повеќе кутии вметнати една во друга. Очигледно, решението на задачата ќе биде да тргнеме со наједонставен пакет кој содржи само една кутија, и потоа пакетот што веќе сме го направиле да го прошируваме така што ќе го вметнеме целиот во нова кутија која го собира, така правејќи нов, поголем пакет. Ајде најпрвин да разгледаме со што се карактеризира еден пакет :

1. димензиите на пакетот, односно димензијата на најголемата кутија во која се вметнати сите други

2. бројот на кутии во пакетот

Така, еден пакет P можеме да го разгледуваме како подреден пар (D, X) каде D = (x, y, z) е подредената тројка од димензиите на пакетот, односно димензиите на кутијата со која „завршува“ пакетот, а X е бројот на кутии во пакетот. Целта на задачата е да се направи најголем пакет, каде под најголем пакет се подразбира пакет со најголем број на кутии, со најголемо X. Доколку двете кутии од примерот погоре ги вметнеме една во друга би направиле пакет од две кутии, P = ((6, 3, 5), 2).

При решавањето, кутиите ќе треба да ги разгледуваме една по една во некаков редослед. На редоследот ќе се вратиме подоцна. Сега да претпоставиме дека ги изминуваме како што треба и да претпоставиме дека сме ги разгледале првите j-1 од сите N кутии и сме успеале да пресметаме кои пакети можат да се направат од нив и ги знаеме атрибутите на тие пакети (димензиите и бројот на кутии во секој од нив). Ја разгледуваме ј-тата кутија. Она што ќе се обидеме да направиме е да ги изминеме сите досега направени пакети и да видиме дали некој од нив можеме да го вметнеме во тековната, ј-та, кутија која ја разгледуваме со цел да направиме поголем пакет. Ако пакетот P = (D, X) може да се вметне во ј-тата кутија, тогаш би добиле нов пакет Q = (E, X+1) каде Е е подредената тројка која ги опишува димензиите на ј-тата кутија. 

За да ваквото решение биде исправно, потребно е да бидеме сигурни дека откако ќе завршиме со обработка на ј-тата кутија никоја од првите j-1 кутии повеќе нема да биде кандидат за можно зголемување на веќе направените пакети, или со други зборови нема да се случи да направиме ние пакет, на пример, од 1-вата, 3-тата и 7-мата кутија и потоа да испадне дека целиот тој може да се смести во 4-тата. Секогаш ќе сакаме веќе направените пакети да можат да се вметнат само во некоја од необработените кутии, односно во некоја од кутиите кои се уште не сме ги изминале.

Како тогаш, кога ќе ја додадеме ј-тата кутија на некој пакет ќе бидеме сигурни дека со ниту една од првите ј-1 кутии тој нема да може да се прошири? Бидејќи има три димензии, единствен критериум кои ги поврзува трите одеднаш е волуменот. И точно, ако кутиите ги сортираме во растечки редослед според волуменот, со сигурност можеме да тврдиме дека пакет со димензија на ј-тата кутија нема да може да се вметне во некоја од првите ј-1 кутии, туку само во некоја од остнатите (од ј+1 - вата до N-тата). Да забележам дека релацијата „x има поголем волумен од y“ помеѓу две кутии x и y не значи нужно дека y може да се вметне во x, туку само дека x не може да се вметне во y. Исто така, кутиите со еднаков волумен нема потреба дополнително да ги сортираме според некој секундарен критериум бидејќи секако не постои случај кога две кутии со ист волумен можат да се сместат една во друга.

Конкретно, би имале една низа B таква што во елементот B[j] ќе ја чуваме максималната големина (Х) на пакетот кој завршува со ј-тата кутија. Оваа максимална големина ќе ја добиеме така што ќе ги изминеме сите досега направени пакети (кои завршуваат со некоја од првите ј-1 кутии и чии максимални големини ги знаеме), секој од нив ќе се обидеме да го вметнеме во ј-тата кутија, и доколку тоа е можно ќе видиме дали неговата големина зголемена за 1 е поголема од големината на веќе направениот пакет кој завршува во ј-тата кутија. На почетокот B[j] = 1 бидејќи секогаш можеме да направиме пакет кој ја содржи само ј-тата кутија и неговата големина е 1. Додека ја обработуваме ј-тата кутија, всушност ќе го бараме најголемиот пакет од веке направените (B[0], B[1], B[2], ... , B[j-1]) кој може да се смести во ј-тата кутија. Ако постојат повеќе такви, вредноста B[j] ќе ја ажурираме согласно. Ако не постои ниту еден, B[j] ќе си остане 1.

Значи, во низата B, eлементот B[j] ќе ја содржи максималната големина на пакетот кој завршува со ј-тата кутија.

Главниот алгоритам би изгледал вака : 

    for (int ј=1;ј<N;ј++)
        for (int k=0;k<j;k++)
              if (vleguva(А[k],А[j]))  B[ј] = max(B[j], B[k]+1);

Надворешниот циклус ги разгледува сите кутии една по една. Внатрешниот циклус ги изминува сите досега направени пакети. Условот е : Ако пакетот кој завршува со k-тата кутија може да се смести во j-тата кутија, тогаш ажурирај ја големината на пакетот кој завршува со ј-тата кутија. Забележете дека пакетот кој завршува со k-тата кутија може да се смести во ј-тата кутија едноставно ако k-тата кутија може да се смести во ј-тата. Алгоритмот претпоставува дека низата со кутии А е сортирана во растечки редослед според волуменот на кутиите, дека B[j] = 1 за секој ј пред почетокот на алгоритмот и дека функцијата  vleguva(x,y) враќа вредност 1 ако кутијата x може да се смести во y со некаква ротација или 0 во спротивно.
На крајот, точниот резултат, односно максималниот број на кутии кои можат да се стават една во друга, се наоѓа некаде низ низата B во зависност од тоа со која кутија завршува најголемиот пакет кој може да се направи. Затоа, потребно ќе биде уште еднаш да ја изминеме низата B и да го најдеме максимумот во неа.

Пример Да разгледаме еден пример. Дадени ни се 4 кутии: (4, 2, 5), (4, 7, 9), (6, 3, 2) и (6, 3, 5). Да ги подредиме најпрво според волуменот.
V0 = 4x2x5 = 40
V1 = 4x7x9 = 252
V2 = 6x3x2 = 36
V3 = 6x3x5 = 90
Кутиите подредени ќе изгледаат :
А0 = (6, 3, 2) (V2)
А1 = (4, 2, 5) (V0)
А2 = (6, 3, 5) (V3)
А3 = (4, 7, 9) (V1)
Низата B на почетокот : B = [1 1 1 1]
Алгоритмот претпоставува дека 0-тата кутија е разгледана, B[0]=1 и циклусот започнува од првата кутија. По секој чекор е дадена состојбата на низата В.

1. j=1, k=0. Дали А0 може да се смести во А1? Не, па најголемиот пакет што завршува со А1 ќе биде со големина 1, и тоа е точно пакетот кој ја содржи само А1, без други кутии во неа.
B = [1 1 1 1]

2. j=2, k=0. Дали А0 може да се смести во А2? Не. Оди на следен пакет (k=1).
B = [1 1 1 1]

3. j=2, k=1. Дали А1 може да се смести во А2? Да. Значи сме успеале веќе пресметаниот најголем пакет што завршува со кутијата А1 и чија големина е запишана во B[1] да го прошириме така што целиот ќе го вметнеме во кутијата А2. Па, соодветно B[2] го ажурираме на max(B[2], B[1]+1) = max(1, 1+1) = max(1, 2) = 2.
B = [1 1 2 1] 

4. j=3, k=0. Дали А0 може да се смести во А3? Да, па ажурирај го B[3] = max(B[3], B[0]+1) = 2.
B = [1 1 2 2]

5. j=3, k=1. Дали А1 може да се смести во А3? Да, па ажурурај го B[3] = max(B[3], B[1]+1) = 2.
B = [1 1 2 2]
Забележете дека во чекор 4 пакетот голем 2 е составен од кутиите А0 и А3, а во чекор 5, пакетот голем 2 е составен од кутиите А1 и А3. Алгоритмот не го интересира кои кутии влегуваат во пакетите, овој коментар е само за илустрација.

6. ј=3, k=2. Дали А2 може да се смести во А3? Да, па B[3] = max(B[3], B[2]+1) = max(2, 3) = 3
B = [1 1 2 3]

Резултатот е максималниот елемент од низата В, а тоа е 3. Можеше да се случи максималниот елемент да не се наоѓа на последна позиција бидејќи не мора да значи дека кутијата со најголем волумен може во себе да собере најмногу други кутии. Пример, (2, 2, 2), (3, 3, 3) и (1, 1, 100). Овдека точниот резултат ќе се наоѓа во B[1], а не во B[2] и покрај тоа што кутијата A2 има најголем волумен V(A2) = 100.
Во прилог е дадена имплементација во C++ на опишаниот алгоритам.

За оние кои повеќе ги интересира, проблемот во суштина претставува барање на најдолг пат во ацикличен граф со динамичко програмирање. Јазлите на графот се кутиите, врска меѓу два јазли x и y постои ако кутијата од јазелот x може да се стави во y, а сортирањето според волуменот претставува едно можно тополошко сортирање на тој граф кое ни гарантира дека во редоследот по кој ги изминуваме јазлите нема да ни се јави врска која ќе не враќа назад кон веќе изминатиот дел од графот. Овој проблем е варијација на основниот проблем од овој тип - LIS (longest increasing subsequence).
Временската сложеност на алгоритмот е О(N²).  LIS проблемот може да се реши и во О(NlogN) време.


boxes.cpp
PDF  http://www.mediafire.com/download.php?dwhaqs7mtp6vtpx

AlStrPo, динамичко, програмирање, longest, increasing, subsequence