- Miért nem lehet az ismétlés nélküli hátizsák feladatnál is egyszerűen a pénzváltási feladatnál ill. ismétléses hátizsáknál megismert kapacitáscsökkentéses részproblémára bontást alkalmazni?

A pénzváltási és ismétléses hátizsák feladatoknál a tárgyakból végtelen darabszámú áll rendelkezésre, ezért ha a kisebb részfeladat optimális megoldását egészítjük ki azzal, hogy az i. tárgyból még egy darabot hozzáteszünk azzal megkaphatjuk a nagyobb probléma egy optimális megoldását.
Az ismétlés nélküli esetben azonban ha az i. tárgy szerepel a kisebb kapacitásra adott optimális megoldásban, akkor nem vehetem be még egyszer az i. tárgyat a nagyobb probléma megoldásába (hiszen akkor már kétszer szerepelne az i. tárgy). Azaz ezzel a stratégiával nem tudom részproblémá optimális megoldásából egyszerűen kiszámolni a nagyobb probléma optimális megoldását.
Viszont ha úgy bontunk kisebb problémákra, hogy a kapacitás is kisebb és a rendelkezésre álló tárgyak halmaza is kisebb akkor már adható egyszerű módszer a nagyobb problém optimális megoldásának megszerkesztésére.