Érdekel mire gondol egy igazi programozó vasalás közben?
Adott a vasalni való. A vasalandó ingek vállfán érkeznek, egy vállfán 1..n vasalandó ing lehet, egy vasalás alkalmavál 1..m vállfa érkezik. Vasaláskor 1 inget veszel le egy tetszőleges vállfáról, ez csak a legfelső lehet, kivéve, ha az adott vállfán csak két ing van a levétel előtt, ekkor bármelyiket el lehet kezdeni vasalni. Az inget vasalás után egyből vissza kell rakni egy másik vállfára és felakasztani a szekrénybe. A szekrényben 0..l darab szabad válfa van. Egyszerre vasalt ing egy vállfán k darab lehet (speciális eset: k=1,2). Ha k>1, akkor szekrényben olyan vállfa is található, amin már van vasalt ing. Az ingek osztályokba vannak sorolva, egy vállfára csak ugyanabból az osztályból származó vasalt ingek kerülhetnek.
Kérdések:
- A paraméterek milyen értékei mellett van végrehajtható vasalási terv?
- A paraméterek milyen értékei mellett hajtható végre minden vasalási terv?
- A paraméterek milyen értékei mellett NP nehéz probléma a vasalási terv kialakítása? (Egyáltalán ez NP nehéz probléma?)
Megjegyzés: köznap életben előforduló értékek mellett a feladat megoldható (nekem legalábbis hetente 1-2 alkalammal menni szokott).
