Vieme, že nejaké “najhoršie” riešenie bude, že každý kostým bude na jednom lane. Keďže sa všetky kostýmy sušia naraz, tak celkový čas sušenia bude vždy rovnaky ako čas sušenia toho “najpomalšieho” kostýmu. Ak by sme tento čas chceli vylepšiť, tak jediná možnossť je, že zoberieme najpomalší kostým a prevesíme ho cez obe laná.

Všetky kostýmy povešané cez obe laná budeme ukladať na začiatok lán. Vieme, že ak nejaké riešenie bude existovať, tak určite bude existovať rovnako dobré s tým, že kostýmy zavesené na oboch lanách sú na začiatku. Vieme si ich totiž v tom nejakom riešení posunúť na začiatok a stále to bude fungovať. Naopak to však nemusí platiť. Každé optimálne riešenie teda vieme poposúvať tak, že na začiatku bude niekoľko kostýmov na oboch lanách a potom zvyšok bude zavesený na jednom lane.

Tieto pozorovania využijeme pri zisťovaní riešenia. Začneme s “najhorším” riešením a postupne ho budeme vylepšovať. Jeden krok vylepšenia je, že si zoberieme ten najpomalší kostým a prehodíme ho cez obe laná. Preto si kostýmy utriedime podľa pomalšieho času, aby sme vedeli rýchlo povedať, ktorý z nich máme prehodiť. Povedzme, že prvých niekoľko kostýmov na oboch lanách nám zaberie šírku $x$. Na zvyšok potom ostáva $2l - x$ lana. V každej iterácii vylepšovania potrebujeme zistiť, či vieme rozvešať zvyšné kostýmy. Naša úloha sa teda zjednodušuje na to, že kostýmy vešiame iba na jedno lano a chceme zistiť, či sa dajú povešať na dve laná s dĺžkou $l - x$. V nasledovnej časti riešime, iba to, ako zodpovieme túto otázku.

Bruteforce

Najprv môžeme vyskúšať priamočiary prístup. Pre každé $k$ vezmeme zvyšných $n-k$ kostýmov a vyskúšame všetky možné rozdelenia na prvé a druhé lano. Pre každú podmnožinu spočítame sumu šírok. Ak sa táto suma zmestí do zostávajúcej kapacity prvého lana a zvyšok sa zmestí do kapacity druhého lana, našli sme platné rozdelenie. Pre každé z $n$ možných umiestnení hranice generujeme všetky podmnožiny, čo trvá $O(2^{n-k})$. Celkovo teda $O(n \cdot 2^n)$.

Takmer optimálne riešenie

Problém rozdelenia zvyšných kostýmov na dve laná je podobný známemu problému batohu (Knapsack problem). Môžeme použiť dynamické programovanie. Budeme mať tabuľku $dp$, kde $dp[i][j]$ bude true práve vtedy, ak je možné zaplniť šírku $j$ na prvom lane len s prvými $i$ kostýmami. Túto tabuľku vieme jednoduchým prechádzaním dopĺňať - $dp[i][j] = dp[i-1][j] \lor dp[i-1][j-w_i]$. Znamená to, že buď sme danú šírku $j$ na prvom lane dosiahli už s prvými $i-1$ kostýmami, alebo sme použili $i$-ty kostým so šírkou $w_i$ a potrebujeme doplniť šírku $j-w_i$ z $i-1$ kostýmov, čo už máme vypočítané. Je jasne vidno, že tabuľku si vieme vyplniť v čase $O(n \cdot l)$, keďže každý prvok tabuľky sa vypočíta v konštantnom čase. Odpoveď na otázku, či vieme kostýmy doplniť na dve laná bude, že prejdeme cez všetky dosiahnuteľné šírky na prvom lane (tie, kde $dp[n][j]$ je true) a zistíme, či sa šírka zostávajúcich kostýmov (tých, ktoré nie sú na oboch lanách a ani na prvom) zmestí na druhé lano. Celková časová zložitosť tohto riešenia je $O(n^2 \cdot l)$, lebo pre každý počet kostýmov na začiatku musíme spúšťať tento problém batoha nanovo.

Pamäťová zložitosť by bola $O(n \cdot l)$, lebo to je veľkosť našej tabuľky. Všimnime si, že na zistenie nového stĺpca potrebujeme len ten predošlý. Takže zvyšné si nemusíme pamätať, lebo ich už nebudeme potrebovať pri ďalších výpočtoch. To nám zníži pamäťovú zložitosť na $O(l + n)$, lebo si pamätáme jeden stĺpec tabuľky a usporiadané kostýmy.

Optimálne riešenie

V predošlom riešení sme pri každom pridaní kostýmu na obe laná znova počítali rozdeľovanie takmer tých istých kostýmov. Konkrétne pri každej iterácii sa odobral jeden kostým z jedného lana a prehodil na dve. To znamená, že počet kostýmov v “batohu” sa nám postupne odoberal. Keď sa pozrieme bližšie na problém batoha, tak by sa nám hodilo keby sa kostýmy postupne pridávali. Pridanie kostýmu nebude znamenať všetko prepočítať, ale dopočítať jeden stĺpec.

Skúsme teda otočiť poradie vonkajšieho cyklu - namiesto pridávania kostýmov na obe laná začneme s tým, že všetky už sú na oboch lanách, a budeme ich odoberať. To nám spôsobí, že pri batohu nám budú kostýmy pribúdať a po prehodení kostýmu stačí dopočítať jeden stĺpec. Takže sme sa posunuli z času $O(n^2 \cdot l)$ na $O(n \cdot l)$. Pamäť zostáva rovnaká ako v minulom riešení.