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.