2. Domácí úkol - seřazení vagónů vlaku

Čtěte prosím tuto stránku celou a pozorně.

Zadání

Napište program, který spočítá, jak seřadit vagóny vlaku tak, aby pod vlakem nespadnul most.

Program má na vstupu následující údaje:

• seznam vah jednolivých vagónů,
• k - počet vagónů na jednom mostním oblouku, jede-li vlak přes most,
• m - maximální nosnost mostního oblouku.

Výstupem programu by měla být posloupnost vah vagónů seřazená tak, aby při průjezdu vlaku přes most nikdy nedošlo k překročení nostnosti oblouku. Jinými slovy: najděte permutaci vstupní posloupnosti čísel takovou, že žádná její podposloupnost (ve smyslu podinterval) délky k nemá součet vyšší než m.

Můžete předpokládat, že počet vagónů je větší nebo roven k.

Formát vstupu a výstupu

Vstupní soubor vstup.txt obsahuje dva řádky. Na prvním řádku jsou váhy vagónů oddělené mezerami. Maximální počet vagónů je 100. Na druhém řádku jsou dvě čísla oddělená mezerou. První z nich je počet vagónů na mostním oblouku k, druhé z nich je maximální nosnost oblouku m.

Výstupem je soubor vystup.txt, který obsahuje jeden řádek s váhami vagónů oddělenými mezerami. V případě že vagóny pro daný most seřadit nelze, obsahuje soubor jeden řádek se slovem NELZE.

Ukázkové vstupní a výstupní soubory si můžete stáhnout zde: data.tar

Soubory ve formátu .tar lze rozbalit například Total Commanderem, nebo pomocí programu tar.exe příkazem "C:\>tar.exe xvf data.tar". Více informací o použití programu tar najdete zde.

Algoritmus

Problém lze řešit pomocí klasického backtrackingu s prořezáváním.

Jedna z možných implementací spočívá v postupném připojování vagónů k vlaku všemi možnými způsoby. Během připojování je možné kontrolovat, zda posledních k vagónů nepřekročilo nosnost oblouku m. Pokud je nosnost překročena, nemá smysl zkoušet připojit další vagóny.

Vyšší efektivity programu (pro případy kdy existuje řešení) lze dosáhnout tím, že algoritmus bude napřed zkoušet připojit ty nejtěžší vagóny. Při této strategii se problémy s váhou projeví dříve a prořezávání bude účinnější. Výběr nejtěžšího nevyzkoušeného vagónu je potřeba implementovat efektivně, pomůže například sestupné seřazení vah vagónů na začátku programu.

Ukázková data

Příklady souborů s výstupem najdete v archivu data.tar.

Poznámky

• Formát vstupu a výstupu je povinný, jeho nedodržení je považováno za chybu.
• Program by kromě vstupního textového souboru neměl požadovat žádná data (ani z klávesnice).
• Do programu prosím vložte komentář se svým jménem a příjmením.
• Řešení posílejte mailem na adresu hruska (zavináč) popelka (tečka) ms (tečka) mff (tečka) cuni (tečka) cz s předmětem zprávy PGM - vlak a s přiloženým souborem vlak.pas.
• Po odeslání mailu s domácím úkolem by vám měla přijít zpět zpráva s potvrzením příjmu.
• Neposílejte .exe soubory.
• V případě jakýchkoliv nejasností nebo problémů mi pošlete mail.

Termíny

Termín zadání: 24.11.2006.
Termín odevzdání: do 10.12.2006 včetně.
Termín odevzdání oprav: do 17.12.2005 včetně.