NézetNyomtat

Pakolás (Megoldás)
Elmélet > Algoritmusok > Dinamikus programozás
Címkék > Feladat

Pakolás

Kamionnal kell elszállítani tárgyakat. Ismerjük a kamion kapacitását, tehát azt a súlyt, amelynél több nem rakható a kamionra, és ismerjük az elszállítandó tárgyak súlyát. Az a cél, hogy a kamiont úgy pakoljuk meg tárgyakkal, hogy az összsúly a lehető legnagyobb legyen.

Feladat

Készíts programot (PAKOL.PAS, ...), amely kiszámítja, hogy mekkora az a legnagyobb összsúly, amit a kamionnal elszállíthatunk! A program adja meg, hogy mely tár­gyak kamionra rakásával érhető ez el.

Bemenet

A PAKOL.BE szöveges állomány első sorában két egész szám van, a tárgyak $N$ száma $(1\leq N\leq 100)$ és a kamion $K$ kapacitása $(1\leq K\leq 600)$. A második sor pontosan $N$ pozitív egész számot tartalmaz egy-egy szóközzel elválasztva. Az $I$-edik szám az $I$-edik tárgy súlya, ami nem nagyobb, mint a kamion $K$ kapacitása.

Kimenet

A PAKOL.KI szöveges állomány első sorába a kamionnal elszállítható legnagyobb $S$ összsúlyt kell írni! A második sorba az $S$ összsúlyt adó pakolásban szereplő tárgyak $M$ számát kell írni! A harmadik sorba a kamionra pakolt $M$ tárgy sorszámát kell írni tetszőleges sorrend­ben, egy-egy szóközzel elválasztva! Több megoldás esetén bármelyik megadható.

Példa

PAKOL.BEPAKOL.KI
6 20
18 12 4 7 10 5
19
3
3 6 5

Tesztadatok