Van N darab téglatest alakú dobozunk, mindegyiknek ismerjük a méreteit. A dobozokat egymásba szeretnénk pakolni, hogy minél kevesebb helyet foglaljanak. Egy dobozba olyan másik doboz tehető, amelynek mindhárom mérete kisebb az adott doboz méreteinél, de a dobozok tetszőlegesen forgathatók (azaz pl. egy (7,5,3) méretű dobozba betehető egy (4,2,6) méretű doboz).
Feladat
Készíts programot, amely kiszámítja a legtöbb dobozból álló dobozsorozatot, amelyek egymásba pakolhatók! Bemenet
A standard bemenet első sorában a dobozok száma (1 < N ≤ 2000) van. A következő N sor mindegyike három pozitív egész számot tartalmaz (egy-egy szóközzel elválasztva), az egyes dobozok méretét (1 ≤ xi , yi, zi ≤ 10 000). Az i-edik sorban az i-edik doboz leírása szerepel. Kimenet
A standard kimenet első sorába a legtöbb dobozból álló dobozsorozat H elemszámát kell írni, amelyek egymásba pakolhatók! A következő sorba pontosan H számot kell írni egy-egy szóközzel elválasztva: a leghosszabb ilyen dobozsorozatban szereplő dobozok sorszámait! Az első legyen közülük a legnagyobb doboz, s minden dobozt egy olyan kövessen, amely az adott dobozba belefér! Több megoldás esetén bármelyik megadható. Példa
| Bemenet |
Kimenet |
6
2 3 8
1 4 2
4 2 7
2 1 3
5 3 9
1 2 3 | 3
5 3 2
|
Tesztadatok
További tesztadatok: mester.inf.elte.hu
Címkék
A feladat forrása: mester.inf.elte.hu, haladó > rekurzív kiszámítás > dobozok
Algoritmusok: mélységi bejárás, topologikus rendezés, leghosszabb út DAG-ban
megoldás | 
2004-2016 BDG algoritmus szakkör