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.

Készíts programot, 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.

A PAKOL.BE szöveges állomány első sorában két egész szám van, a tárgyak N száma (1 <= N <= 100) és a kamion K kapacitása (1 <= K <= 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.

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ó.

Bemenet	Kimenet
6 20 18 12 4 7 10 5	19 3 3 6 5

A feladat forrása: NTOISZTV 2008, 2. forduló, 11-13. évfolyam

Algoritmusok: inamikus progrmozás

megoldás