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

Opdrachten dynamisch programmeren

1. Je hebt een rugzak dat een maximum gewicht kan dragen. Er zijn items die je in je rugzak kan stoppen. Elk item heeft een waarde en gewicht. Bereken de maximale waarde die je in je rugzak kan stoppen zonder dat deze te zwaar wordt. Elk item kan je of volledig in je rugzak stoppen of niet in je rugzak stoppen. Het is niet mogelijk een gedeelte van het item te gebruiken en je mag een item niet meerdere keren in je rugzak stoppen.

   Invoer

   - Eerste regel is het gewicht van de rugzak, dit is altijd een geheel getal - Tweede regel is het aantal items n - Op de derde regel staan n gehele getallen gescheiden met een spatie: dit zijn waardes van de items - Op de vierde regel staan n gehele getallen gescheiden met een spatie: dit zijn de gewichten van de items

   Voorbeeld invoer: 10 4 10 40 30 50 5 4 6 3 Voorbeeld uitvoer: 90 Met de volgende link kan je testen of je programma werkt: rugzak.

2. Er zijn N stenen genummerd van 0 t/m N-1, elke steen i heeft een hoogte hi. Er is een kikker die op steen 0 staat. De kikker kan naar steen i + 1 of i + 2 springen. De kosten voor deze sprong zijn |hi – hj|, steen j is de steen waar de kikker heen springt. Uitvoer: de minimale kosten voor de kikker om naar steen N-1 te springen. Voorbeeld invoer: 4 -> dit zijn het aantal stenen 10 30 40 20 -> dit zijn de hoogtes van de stenen Voorbeeld uitvoer: 30 Met de volgende link kan je testen of je programma werkt: kikker.
3. Bibi maakt plannen voor haar vakantie. Haar vakantie duurt N dagen. Voor elke dag i kan ze kiezen uit de volgende activiteiten: Zwemmen in de zee, hier krijgt ze ai gelukspunten voor Wandelen in de bergen, hier krijgt ze bi gelukspunten voor Boek lezen, hier krijgt ze ci gelukspunten voor Bibi verveelt zich snel en kan niet twee dagen achter elkaar dezelfde activiteit uitvoeren. Uitvoer: Bereken de maximaal aantal gelukspunten dat Bibi kan verdienen tijdens haar vakantie. Voorbeeld Invoer 3 -> dit zijn het aantal dagen vakantie 10 40 70 -> dit zijn de gelukspunten voor dag 1 van activiteit a, b en c. 20 50 80 30 60 90

   Voorbeeld Uitvoer 210

4. Er zijn N kinderen genummerd 1 t/m N. Er zijn K snoepjes. De snoepjes moeten verdeeld worden over de kinderen waarbij elk kind i tussen de 0 en a snoepjes moet ontvangen. Er mogen geen snoepjes overblijven. Uitvoer: berekenen het aantal manieren dat je de snoepjes over de kinderen kan verdelen, modulo 109+7.

   Voorbeeld invoer 3 4 -> het aantal kinderen en het aantal snoepjes 1 2 3 -> het maximaal aantal snoepjes dat een kind mag ontvangen

   Voorbeeld uitvoer 5

5. Maak de opgave beeldhouwer. Dit is een van de opgaves van de IOI 2004 in Griekenland.

---