Problem: Givet en heltalsarray A[1..n] och ett heltal s, bestäm huruvida man kan skriva s som en summa av element i A, om varje element får användas högst en gång!
Ex. Om A = {4,7,10} blir resultatet JA för s = 0, 4, 7, 10, 11, 14, 17 eller 21 men NEJ för t.ex. s = 9.
Problemet kan givetvis lösas rekursivt. T.ex.
Knap_rek(A,start,s)
if s = 0 then ***JA***
else if s > 0 then
for a := start to length[A] do
Knap_rek(A, a+1, s-A[a])
som anropas med start = 1. (a+1 i anropet är för att varje element bara får användas en gång och för att inte få med några dublettlösningar 4+7 = 7+4)
Problemet med denna lösning är att den blir ineffektiv om arrayen är lång, eftersom den är exponentiell. Anledningen till att den rekursiva algoritmen är ineffektiv är egentligen att om talet s är någorlunda litet kommer vi ofta att nå fram till samma resultat på många olika sätt. Detta motsvaras av att proceduren kommer att anropas flera gånger med exakt samma parametrar.
Ex. Om A = {1,1,3} och s = 3 kommer proceduren att både testa att ha med första ettan men inte andra, samt att ha med andra men inte första, vilket ger två indentiska anrop Knap_rek(A,3,2). En effektivisering skulle alltså vara att spara värdet på Knap_rek(A,3,2) (=NEJ) i en tvådimensionell matris. Innan man gör rekursionen kollar man i tabellen om detta anrop redan har gjorts för i så fall är det ju himla onödigt att återigen räkna ut samma sak.
Om man gör den enkla förändringen så har det hux flux blivit dynamisk programmering. Det går ut på att spara "mellanresultat" i någon slags tabell så att man inte gör om samma sak flera gånger. Kanske inte låter så sensationellt, men man kan visa att algoritmen ändras från exponentiell till polynomisk, och om s är tillräckligt litet går det garanterat snabbare.
Men det som gör dynamisk programmering ännu mer användbart är att man ofta kan skriva om koden så att man slipper rekursiva anrop med risk för fel, och istället få en robust, tydlig algoritm som går snabbt att skriva, vilket ju är väldigt viktigt på tävlingar.
Vi behöver en boolean-array B[0..s] (alltså får inte s vara för stort)
Knap_dyn(A,s)
B[1..s] = false
B[0] = true
for a := 1 to length[A] do
for b := 0 to s do
if B[b] and b + A[a]
<= s then B[b+A[a]] := true
if B[s] then ***JA***
Vi har alltså en array som säger huruvida det är möjligt att nå en viss summa med hjälp av de element i A som hittills har genomgåtts. När man sedan tar nästa element A[a] utnyttjar man att om summan b gick att bilda innan så går b+A[a] att bilda nu. Enkelt men smart. Märk att efter looparna är genomgångna, innehåller B resultatet för alla värden på summan mellan 0 och s, vilket kan vara användbart ibland.
Övningsuppgift 1
Ofta ska man i Knapsack-problemet inte bara säga OM det går
att bilda summan, utan även ge ett exempel på ett sätt
att göra detta. Om A={4,7,10} och s = 17 ska man säga
att 17 = 7 + 10. Detta görs lätt genom att använda en heltalsarray
istället
för bara en booleanarray och på något sätt hela
tiden spara hur man bildar varje möjlig summa. Ett annat, mer
generellt sätt är att använda en tvådimensionell matris
med en separat rad för varje element i A.
Ändra algoritmen så att den klarar av ovanstående, både genom att använda heltalsarray (1 X s) och att köra med booleanmatris (length[a] X s).
Övningsuppgift 2
Knapsack-problemet handlar ju egentligen om att packa en ryggsäck med saker av olika storlek. En vanlig variant är att varje sak förutom en storlek har ett "nyttovärde", och så gäller det att packa ryggsäcken med saker så att de får plats (inte nödvändigtvis fullt i ryggsäcken) och så att den totala nyttan, summan av nyttovärdena för de valda sakerna, maximeras. Lös detta problem med dynamisk programmering.