16. Dynamisch programmeren

Het is idee van dynamisch programmeren is dat je een probleem in stappen oplost. Bij een recursief probleem kan het gebeuren dat veel berekeningen dubbel worden uitgevoerd. Dynamisch programmeren kan dan een oplossing zijn. Hieronder wordt het uitgelegd aan de hand van een voorbeeld. Invoer: - Waardes van verschillende munten. Bijvoorbeeld: 1, 3, 4, 5. Van elke munt heb je er oneindig veel. - Een totaalbedrag dat je moet betalen. Bijvoorbeeld: 7 Uitvoer: Het minimale aantal munten waarmee je het totaalbedrag precies kan betalen

We kunnen dit probleem met recursie oplossen.

#include <iostream>
using namespace std;
 
int munt[] = { 1, 3, 4, 5 };
int totaalBedrag = 7;
const int max_waarde = 9999;
 
int dfs(int bedrag){
    if (bedrag < 0) return max_waarde;
    if (bedrag == 0) return 0;
    int besteOplossing = max_waarde ;
    for (int m: munt) {
        besteOplossing = min (besteOplossing, dfs(bedrag - m) + 1);
    }
    return besteOplossing;
}   
 
int main() {    
    cout << dfs(totaalBedrag) <<endl; 
    return 0;
}

Hieronder de boomstructuur van de oplossing met totaalbedrag 7 en de munten: 1, 3, 4 en 5.

In de boom hierboven kan je zien dat in de depth first search oplossing je meerdere keren dezelfde berekening uitvoert. Hieronder worden 2 oplossingen beschreven hiervoor.

Recursie met memorization

Het idee van memorization is dat je deeloplossingen opslaat zodat je ze later weer kunt gebruiken en ze niet weer opnieuw hoeft te berekenen. Hiervoor gebruiken we een array om de oplossingen tussendoor op te slaan. In onderstaand voorbeeld gebruiken we de array "alBerekend" om aan te geven of een oplossing al een keer berekend is. De array "oplossing" bevat de oplossing van het deelprobleem.

#include <iostream>
using namespace std;

const int max_waarde = 9999;
int munt[] = { 1, 3, 4, 5 };
int totaalBedrag = 7;
bool alBerekend[4];
int oplossing[4];
 
int dfs(int bedrag) {
    if (bedrag < 0) return max_waarde;
    if (bedrag == 0) return 0;
    if (alBerekend[bedrag]) return oplossing[bedrag];
    int besteOplossing = max_waarde;
    for (int m: munt) {
        besteOplossing = min (besteOplossing, dfs(bedrag - m) + 1);
    }
    alBerekend[bedrag]  = true;
    oplossing[bedrag]   = besteOplossing;
    return besteOplossing;
}   
 
int main() {    
    cout << dfs(totaalBedrag) <<endl; 
    return 0;
}

Dynamisch programmeren

Bij dynamisch programmeren beginnen we onderaan de boom en werken we naar boven (bottom-up). Noem de oplossing van het probleem waarbij je N euro (N = 7) wisselt met munten van 1, 3, 4 en 5 euro DP[n]. (DP voor dynamisch programmeren).

DP[0] = 0 DP[1] = 1+DP[0] DP[2] = 1+ DP[1] DP[3] = 1+ min(DP[2], DP[0]) DP[4] = 1 + min(DP[3], DP[1], DP[0]) Etc… Uiteindelijk krijg je dan: DP[N]= 1+ min(DP[N-1], DP[N-3], DP[N-4], DP[N-5]) De code hiervoor is:

    dp[0] = 0; 
    for (int bedrag = 1; bedrag<= totaalBedrag; bedrag++ ){
        dp[bedrag] = max_waarde;
        for (int m: munt){
            if (bedrag - m >= 0){
                dp[bedrag] = min(dp[bedrag], dp[bedrag - m] + 1);
            }
        }
    }  

DP[7] bevat dan het antwoord waar we naar op zoek zijn. Het voordeel van dynamisch programmeren is dat de code kort, snel en makkelijk te implementeren is. Het is alleen niet altijd makkelijk te zien hoe je probleem met dynamisch programmeren kan oplossen. De dynamische oplossing is veel sneller dan de depth first search oplossing, omdat er geen dubbele berekeningen worden uitgevoerd. Daar staat tegenover dat de dynamische oplossing meer geheugenruimte vereist, om de tabel met deeloplossingen op te slaan.

Opdracht 16.1 Maak de opdracht: rugzak.

Opdracht 16.2 Maak de opdracht: kikker. Opdracht 16.3 Maak de opdracht: vakantie.

Opdracht 16.4 Maak de opdracht: beeldhouwer. Dit is een van de opgaves van de IOI 2004 in Griekenland.

---