A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre. A feladat szövegét kétféleképpen is értelmezhetjük. A megoldók többségének a felfogása szerint a teherautóknak meghatározatlan mennyiségű, legfeljebb 1 tonnás csomagokból kell minél többet elszállítania. A másik értelmezés szerint a szállítmány eleve adott, és valamennyi csomagot el kell szállítani. Úgy is képzelhetjük a dolgot, hogy a szállító és a megrendelő tárgyal. Az első esetben a szállító csak annyit tud, hogy a szállítmány legfeljebb egy tonnás részekből áll, így kell nyilatkoznia arról, hogy mekkora teher fuvarozását vállalja. A második esetben a megrendelő ajánlata az elszállítandó súlymennyiséget is tartalmazza, a szállítónak arra kell felelnie, vállalja-e a szállítást vagy sem. Mindkét esetben azt a legnagyobb terhet keressük, amit a szállító el tud vinni a megrendelő minden mesterkedése ellenére. A két eset közt a döntő különbség, hogy a másodikban a megrendelő csak az előzetesen kialkudott súlymennyiséget oszthatja részekre, míg az elsőben ilyen megkötés nincs. Ha a csomagok nehezebbek 3/4 tonnánál, akkor egy teherautóra legfeljebb három csomag rakható fel. Megmutatjuk, hogy az első változat szerint tonnánál többet a szállító nem mindig tud elvinni. Tegyük fel, hogy tonna súly elszállítására vállalkozott a szállító, ahol . Ha most a megrendelő súlyú csomagokat készít, akkor teljesítette a feltételt: , másrészt legfeljebb csomag, azaz tonna súly fér el a teherautókon. Látható, hogy a megrendelő ellenintézkedése ‐ a ládák alkalmas becsomagolása ‐ függ a sofőrök ajánlatától. Ha a szállító legfeljebb tonna teher elszállítására vállalkozik, akkor ezt végre is tudja hajtani. Elegendő megmutatnunk, hogy minden teherautóra legalább tonna terhet rakhatunk föl. Rendezzük súly szerint csökkenő sorrendbe a csomagokat és kezdjük őket felrakni az autóra egészen addig, amíg a soron következő már nem fér el. Ha a lemaradt csomag súlya legfeljebb 3/4 tonna, akkor azért nem fért el, mert a kocsin már több, mint tonna teher van. Ha pedig a lemaradt csomag súlya több 3/4 tonnánál, akkor a kocsin levő csomagok is nehezebbek 3/4 tonnánál. Egyetlen csomag sem lehet ugyanakkor nehezebb, mint 1 tonna, a kocsin így legalább három csomag, vagyis több, mint tonna teher van. Ez azt jelenti, hogy öt teherautón mindenképpen elfér tonnánál nehezebb szállítmány is, ezt azonban a szállító nem tudja kihasználni. A második változatban azonban a megrendelőt köti az elszállítandó teher mennyisége. A fenti gondolatmenet szerint az első négy teherautón most is több, mint tonna szállítmány helyezhető el. Ez azt jelenti, hogy a második esetben a szállító 12 tonnát is elvállalhat, hiszen az ötödik teherautóra a megmaradt legfeljebb 3 tonna felrakható. Ennél nehezebb szállítmányt már a második esetben sem vállalhat a szállító. Készíttessen ugyanis a megrendelő 16 darab 3/4 tonnánál nehezebb csoragot , amelyek mindegyike természetesen legfeljebb 1 tonna súlyú. Az öt autó ezek közül legfeljebb 15 darabot szállíthat el. Azt kaptuk tehát, hogy az első értelmezés szerint az elszállítható maximális teher legfeljebb tonna, a második szerint pedig 12 tonna.
|