Tällä viikolla jatkamme dynaamisen ohjelmoinnin harjoittelua. Tällä viikolla erityisesti Tirakirjan luvun 9 esimerkki repunpakkauksesta on hyödyllinen.

Seuraavaksi käymme läpi yhden lisäesimerkin dynaamisesta ohjelmoinnista.

Tehtävä

Annettuna on joukko kolikoita, joiden arvot ovat \{c_1,c_2,\dots,c_k\}. Tehtävänä on laskea, monellako tavalla kolikoista voi muodostaa rahamäärän n, kun jokaista kolikkoa saa käyttää miten monta kertaa tahansa.

Esimerkiksi jos kolikot ovat \{2,3,5\} ja n=7, vastaus on 5, koska vaihtoehdot ovat 2+2+3, 2+3+2, 3+2+2, 2+5 ja 5+2.

Ratkaisu

Voimme ratkaista tehtävän kahdella for-silmukalla, joista ulompi käy läpi kaikki rahamäärät 1 \dots n ja sisempi käy läpi kolikot. Laskemme jokaiselle rahamäärälle, monellako tavalla sen voi muodostaa kolikoista.

Seuraavassa koodissa d[x] ilmaisee, monellako tavalla rahamäärän x voi muodostaa kolikoista. Alussa asetetaan d[0]=1, koska tyhjän rahamäärän voi muodostaa yhdellä tavalla (ei kolikoita).

d[0] = 1;
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= k; j++) {
        if (i-c[j] >= 0) d[i] += d[i-c[j]];
    }
}
cout << d[n] << "\n";

Muunnelma

Luonteva muunnelma tehtävälle on, että haluamme laskea vain aidosti erilaiset tavat. Esimerkiksi tavat 2+2+3 ja 2+3+2 ovat oikeastaan samat, koska kolikot ovat samat mutta ne ovat vain eri järjestyksessä.

Tässä muunnelmassa esimerkkitapauksen vastaus on 2, koska erilaiset tavat ovat 2+2+3 ja 2+5.

Ratkaisu

Yllättävää kyllä, saamme ratkaistua muunnelman muuttamalla vain vähän aiempaa koodia: riittää vaihtaa keskenään silmukoiden rungot.

d[0] = 1;
for (int j = 1; j <= k; j++) {
    for (int i = 1; i <= n; i++) {
        if (i-c[j] >= 0) d[i] += d[i-c[j]];
    }
}
cout << d[n] << "\n";

Nyt koodi käy läpi kolikot yksi kerrallaan ja jokaisen kohdalla kaikki rahamäärät läpi. Jokaisen kolikon käsittelyn jälkeen taulukko d kertoo jokaisesta rahamäärästä, monellako erilaisella tavalla kyseisen rahamäärän voi muodostaa käyttämällä siihen asti käsiteltyjä kolikkoja.