Tulinpa tässä miettineeksi seuraavaa ongelmaa, kun pohdin miten kuluttaisin lompakkoon kertyneitä pikkukolikoita:
Tiina on kerännyt säästöpossuunsa paljon kolikoita. Tiina haluaa ostaa säästämillään rahoilla 2,30 euroa maksavan karamellipussin. Monellako eri tavalla Tiina voi muodostaa tuon summan säästämistään kolikoista?
Kun kolikoiden määrät ovat järjestyksessä 5c, 10c, 20c, 50c, 1e ja 2e:
Säästetyt kolikot 2, 3, 1, 1, 1, 1 tuottaa 4 eri mahdollista kolikkoyhdistelmää: 2 2 0 0 0 1 0 3 0 0 0 1 2 0 1 0 0 1 0 1 1 0 0 1 Entäpä seuraavat tapaukset, kun halutaan muodostaa suluissa oleva summa? 11, 12, 13, 2, 1, 1 (2,30e) 340, 432, 111, 152, 87, 40 (23e)
Tein pienen ohjelman tällaisten helppojen tapausten laskemiseksi, mutta suuremmat tapaukset muuttuvat hyvin hitaiksi laskea. Pystyykö tätä laskemaan jotenkin paperilla? Tämähän on kaiketi ihan perus diofantoksen yhtälö, mutta pitäisi selvittää ratkaisujen lukumäärä (ax1 + bx2 + cx3 + dx4 + ex5 + fx6 = s
Siinäpä pientä pohdittavaa jos kiinnostaa.
Diofantoksella ongelma tosiaan ratkeaa. Määrität tuosta yhtälöstä tuntemattomat x_1,...,x_6. Sitten otat huomioon ehdon x_i>=0, jolloin voit antaa yleisen ratkaisun vapaille muuttujille ylä- ja alarajoja. Ratkaisut ovat ne jonot (x_1,...,x_6), jotka toteuttavat nuo rajat. Pienillä rahasummilla ratkaisujen lukumäärä on pieni, jolloin kolikkoyhdistelmät ovat lueteltavissa järkevässä ajassa.
Tässä on yksi C-kielinen ratkaisu, joka perustuu dynaamiseen ohjelmointiin:
#include <stdio.h>
/* ostoksen hinta 2,30 euroa */
int rahat = 230 / 5;
/* kolikoiden määrä 6 kpl */
int kmaara = 6;
/* kolikoiden arvot 5-senttisinä */
int arvot[] = {1, 2, 4, 10, 20, 40};
/* kolikoiden määrät */
int maarat[] = {11, 12, 13, 2, 1, 1};
/* taulukko, johon kootaan tuloksia */
int muisti[500][10][500];
int main(void) {
int i, j, k;
int summa;
/* jos hinta on 0, tapoja on aina 1 */
for (j = 0; j < kmaara; j++) {
for (k = 0; k <= maarat[j]; k++) {
muisti[0][j][k] = 1;
}
}
for (i = 1; i <= rahat; i++) {
for (j = 0; j < kmaara; j++) {
for (k = 0; k <= maarat[j]; k++) {
summa = 0;
/* siirrytään yhtä pienempään kolikkoon */
if (j > 0) {
summa += muisti[i]
[j - 1]
[maarat[j - 1]];
}
/* käytetään tätä kolikkoa ostoksessa */
if (k > 0 && arvot[j] <= i) {
summa += muisti[i - arvot[j]]
[j]
[k - 1];
}
muisti[i][j][k] = summa;
}
}
}
printf("%i\n", muisti[rahat]
[kmaara - 1]
[maarat[kmaara - 1]]);
return 0;
}Ohjelman taustalla on seuraava ajatus: Tutkitaan tilannetta, jossa ostoksen hintaa on jäljellä a senttiä, käytettävissä on b pienintä kolikkoa ja korkeinta käytettävissä olevaa kolikkoa on jäljellä c kappaletta. Nyt voidaan joko hylätä korkein kolikko ja tutkia, kuinka monella tavalla sama rahamäärä voidaan muodostaa b - 1 pienimmällä kolikolla, tai käyttää korkeinta kolikkoa, jolloin rahamäärä pienentyy ja korkeinta kolikkoa on yksi vähemmän. Pienempiin kolikoihin voidaan siirtyä vain, jos eri kolikkoja on vielä käytettävissä useita, ja korkeinta kolikkoa voidaan käyttää vain, jos niitä on vielä jäljellä ja kolikon arvo ei ole rahamäärää suurempi. Kun kaikki sellaiset tapaukset, joissa rahamäärä on 0, voidaan muodostaa yhdellä tavalla ja muissa tapauksissa lasketaan yhteen kahden eri vaihtoehdon tuottamat muodostustavat, päästään lopuksi haluttuun tulokseen.
Ohjelman rajoituksena on, että jokainen mahdollinen rahamäärän, käytettävissä olevien kolikoiden määrän ja korkeimman kolikon lukumäärän yhdistelmä täytyy mahtua taulukkoon. Esim. viimeisessä tapauksessa rahamäärä on 2300 senttiä, kolikoiden määrä 6 ja suurin kolikon lukumäärä 432, jolloin taulukon koko on 2300 * 6 * 432 = 5961600 alkiota. Tosin näillä kolikoilla kaikki rahamäärät voidaan jakaa viidellä, jolloin taulukon koko onkin vain 460 * 6 * 432 = 1192320 alkiota. Edelleen taulukko pienentyy, jos eri kolikoille varaa vain niin paljon tilaa kuin niitä on käytettävissä. Tässä tapauksessa 2 euron kolikolle on turha varata 432 alkiota, kun sitä voi käyttää vain 40 kertaa.
Ohjelma ilmoittaa muuten kahden viimeisen tapauksen yhdistelmien määriksi 181 ja 3988338 - onkohan oikein?
Antti Laaksonen kirjoitti:
Ohjelma ilmoittaa muuten kahden viimeisen tapauksen yhdistelmien määriksi 181 ja 3988338 - onkohan oikein?
Samat sain minäkin. Tuollainen ratkaisu on myös nopea verrattuna tällaiseen jossa kokeillaan kaikki yhdistelmät ja kasvatetaan yhdistelmien määrää kun summa on oikea:
#include <stdio.h>
long laske(long n[6], long s)
{
long N = 0;
long k[6];
for (k[0] = 0; k[0] <= n[0]; k[0]++)
for (k[1] = 0; k[1] <= n[1]; k[1]++)
for (k[2] = 0; k[2] <= n[2]; k[2]++)
for (k[3] = 0; k[3] <= n[3]; k[3]++)
for (k[4] = 0; k[4] <= n[4]; k[4]++)
for (k[5] = 0; k[5] <= n[5]; k[5]++)
{
if (5*k[0] + 10*k[1] + 20*k[2] + 50*k[3] + 100*k[4] + 200*k[5] == s) N++;
}
return N;
}
int main(void)
{
long n[6] = {11, 12, 13, 2, 1, 1};
printf("%d\n", laske(n, 230));
return 0;
}Pienillä kolikkomäärillä tietysti käy tämäkin.
Myös 181 ja 3988338 .
Vanha jäi koukkuun. Oli sen verran kiinnostava numerojutska. Tein VB5:llä oheisen viritelmän. Jos lähdekoodi kiinnostaa, voin laittaa linkin kunhan kommentoin hieman. Tässä ratkaisussa periaate on hakea ensin pienimmillä kolikoilla ratkaisu. Sen jälkeen haetaan seuraavat järjestyksessä kunnes viimeisenä saadaan suurimpien kolikoiden ratkaisu.
http://koti.mbnet.fi/kurtan5/Kolikot.exe
Jos lähdekoodi ei ole kovin pitkä, voisit liittää sen myös keskusteluun. Kuinka paljon ohjelmasi käyttää aikaa ja kuluttaa muistia? Ajatus muodostaa lopullinen ratkaisu pienemmistä ratkaisuista on joka tapauksessa sama kuin minun koodissani.
Ohjelmassani oli joitain bugeja jotka korjasin. Ohjelmassa ei tarvita muita taulukoita kuin kolikoiden arvot, määrät ja max.määrät. Lisään vielä aikamittauksen mukaan. Laskennan nopeuttamiseksi doeventsiä käytetään vain joka 1000:lla kierroksella ja välituloksia näytetään 0,2 sekunnin välein. Liitän linkin lähdekoodiin kohtapuoliin.
Lisäsin aikalaskennan ja kommentit. Koodi on aika pitkä koska mukana on käyttöliittymän sälää. Aikaa meni tuohon jälkimmäiseen 0,05 s.
Tässä:
(Mod. poisti lähettäjän pyynnöstä, ks. alla.)
Virheiden määrä on näemmä verrannollinen tiettyyn iän potenssiin. Yllä olevassa koodissa on paha kirjoitusvirhe ja koko koodin voi poistaa. Korjatun exen ja lomaketiedoston saa linkeistä:
http://koti.mbnet.fi/kurtan5/Kolikot.exe
http://koti.mbnet.fi/kurtan5/frmKolikot.frm
Mielestäni tätä kolikkotehtävää olisi voinut ehdottaa vaikka putkapostiin koska vieläkin löytyi virheitä. Nuo edelliset ratkaisut antoivat oikean tuloksen useinmiten mutta joskus väärän. Siksi en heti huomannut virhettä. Nykyinen versio näyttää toimivan oikein. Mutta eipä tämä aihe näytä enää kiinnostavan muita. En saanut Antin ratkaisusta mitään tolkkua ja siksi sain tätä omaani veivata aika pitkään.
Tässä on ohjelmani parannettu versio, joka käyttää vähemmän muistia ja toimii nopeammin.
#include <stdio.h>
/* ostoksen hinta 2,30 euroa */
int rahat = 230 / 5;
/* kolikoiden määrä 6 kpl */
int kmaara = 6;
/* kolikoiden arvot 5-senttisinä */
int arvot[] = {1, 2, 4, 10, 20, 40};
/* kolikoiden määrät */
int maarat[] = {11, 12, 13, 2, 1, 1};
/* tavat muodostaa eri rahamäärät */
int muisti[5000] = {0};
/* uudet tavat muodostaa rahamäärät */
int uusi[5000] = {0};
int main(void) {
int i, j, k;
/* nollan voi muodostaa ilman kolikoita */
muisti[0] = 1;
/* käydään läpi kaikki kolikot */
for (i = 0; i < kmaara; i++) {
/* käydään läpi kaikki rahamäärät */
for (j = 0; j <= rahat; j++) {
/* laitetaan pohjalle aiempi tulos */
uusi[j] = muisti[j];
/* tutkitaan kaikki kolikoiden määrät */
for (k = 1; k <= maarat[i]; k++) {
/* jatketaan, jos rahamäärä ei alita nollaa */
if (j - k * arvot[i] < 0) break;
/* tapojen määrä, kun käytetään k kolikkoa */
uusi[j] += muisti[j - k * arvot[i]];
}
}
/* korvataan vanhat tulokset uusilla */
for (j = 0; j <= rahat; j++) {
muisti[j] = uusi[j];
}
}
printf("%i\n", muisti[rahat]);
return 0;
}Tällä kertaa ajatuksena on käydä läpi kolikot yksi kerrallaan ja laskea, kuinka monta tapaa eri rahamäärien muodostukseen on, kun käytössä on kaikki siihen mennessä käsitellyt kolikot. Kun tutkitaan tiettyä rahamäärää ja tiettyä kolikkoa, voidaan suoraan valita pienempien kolikoiden tulos käyttämättä kolikkoa kertaakaan tai sitten käyttää kolikkoa korkeintaan niin monta kertaa, kuin kolikkoja on yhteensä saatavilla. Laskemalla näiden eri tapausten tulokset yhteen, saadaan laskettua eri tavat muodostaa rahamäärä tämän kolikon ollessa suurin. Tällä toteutuksella taulukkoon tarvitsee enää tallentaa yksi lukumäärä jokaista rahamäärää kohden, joten ohjelman muistinkäyttö pysyy kohtuullisena.
setä kirjoitti:
Mutta eipä tämä aihe näytä enää kiinnostavan muita. En saanut Antin ratkaisusta mitään tolkkua ja siksi sain tätä omaani veivata aika pitkään.
Aihe kyllä kiinnostaa minuakin, mutta en ehtinyt viikolla juuri pohtimaan tehtävää. Minulla taas on hieman vaikeuksia saada selvää sinun koodistasi (koodin ymmärtäminen on tunnetusti vaikeaa, jos koodi ei ole itse tehty), joten olisi mukavaa, jos voisit vielä kuvailla sanallisesti sen toimintaa. Vähäinen muistinkäyttö on mainio piirre ohjelmassa, mutta mitenhän on nopeuden laita?
Tuolla aiemmin kerroinkin, että lähes 4 miljoonan vaihtoehdon laskemiseen meni aikaa 0,05 s. Laskenta nopeutuu huomattavasti, kun Do-silmukassa doevents suoritetaan vain joka 1000:lla kierroksella ja tuloksia päivitetään 0,2 s. välein. Lähinnä tulostus veisi laskenta-ajan noin 10 000-kertaiseksi.
Periaate on erinäisten tarkistusten jälkeen hakea ratkaisu pienimmillä mahdollisilla kolikoilla. Tämä haetaan ottamalla kaikki mahdolliset kolikot käyttöön pienimmistä alkaen kunnes annettu summa saavutetaan tai ylitetään. Sen jälkeen säädetään summa oikeaksi poistamalla ylimääräiset kolikot.
Do-silmukassa haetaan aluksi kolikko, jonka määrää on mahdollista kasvattaa ja korvataan sillä pienempiä kolikoita hakemalla taas alkuun ratkaisu, jossa jäljellä olevista käytetään pienimmät. Jatketaan korvaamalla pienempiä kolikoita suuremmilla järjestyksessä ja laskuria kasvatetaan jokaisella vaihtoehdolla. Laskentaa on vielä nopeutettu 5 ja 10 senttisten kohdalla niin, että vaihtoehtojen määrä lasketaan suoraan eikä askelleta yksittäin. Laskenta päättyy kun ei ole enää lisättäviä kolikoita tai lisättävän kolikon arvo ylittää annetun summan.
Antin koodi on kyllä selkeätä mutta kun en ole perehtynyt C-kieleen niin en saa siitä selvää.
Käy rekursiivisesti läpi eri kolikkomäärien yhdistelmiä, mutta karsii pois mahdottomiksi "huomaamansa" vaihtoehdot (summa kasvaa liian suureksi tai jäljellä oleva rahamäärä ei riitä). Tämä on selkeästi hitaampi kuin Laaksosen koodi mutta myös selkeästi nopeampi kuin KemXy:n versio (johtuen ilmeisesti karsinnasta). Ilman karsintaa aikavaativuus kait eksponentiaalinen eli kolikkotyyppien suhteen ja lineaarinen kolikkojen määrän suhteen (tjsp). En sitten tiedä, miten tuo karsinta vaikuttaa tuohon, veikkaisin suuruusluokan pysyvän samana.
Ja koodi:
#include <stdio.h>
/* ostoksen hinta 2,30 euroa */
int rahat = 230 / 5;
//int rahat = 2300 / 5;
/* kolikoiden määrä 6 kpl */
int kmaara = 6;
/* kolikoiden arvot 5-senttisinä */
int arvot[] = {1, 2, 4, 10, 20, 40};
/* kolikoiden määrät */
int maarat[] = {11, 12, 13, 2, 1, 1};
//int maarat[] = {340, 432, 111, 152, 87, 40};
/* saatujen yhdistelmien määrä */
int yhdistelmia = 0;
/**
* kolikko: kolikkotyyppi, jota tarkastellaan
* valittu: tähän mennessa valituista kolikoista muodostuva yhteissumma
* jaljella: paljonko on vielä rahaa jäljellä
**/
void laskeYhdistelmat(int kolikko, int valittu, int jaljella) {
int i, minValittava;
/* seuraavan kolikon tapauksessa kaikki nämä kolikot on jo käytetty */
jaljella -= maarat[kolikko] * arvot[kolikko];
/* pienin mahdollinen määrä näitä kolikoita, jolla summa voidaan saavuttaa */
minValittava = (rahat - (valittu + jaljella) + (arvot[kolikko] - 1)) / arvot[kolikko];
if( minValittava < 0 )
minValittava = 0;
valittu += minValittava * arvot[kolikko];
/* käydään tämän kolikon mahdolliset eri lukumäärät läpi */
for( i = minValittava; i <= maarat[kolikko] && valittu <= rahat; ++i ) {
/* saavutettiinko summa? */
if( valittu == rahat ) {
++yhdistelmia;
return;
}
/* kokeillaan tällä määrällä näitä kolikoita eri loppujen kolikoiden yhdistelmät */
laskeYhdistelmat(kolikko + 1, valittu, jaljella);
valittu += arvot[kolikko];
}
}
int main(void) {
int i, yhteensa;
/* paljonko rahaa yhteensä */
yhteensa = 0;
for( i = 0; i < kmaara; ++i )
yhteensa += maarat[i] * arvot[i];
/* lasketaan yhdistelmat */
laskeYhdistelmat(0, 0, yhteensa);
printf("%i\n", yhdistelmia);
return 0;
}Tämä on Haskellia. Ohjelma on aika nirso komentoriviargumenttien suhteen. Niiden pitää olla sellaisia, että aluksi on lista, jossa ei ole välilyöntejä ja sitten kohdeluku senteissä. Siis näin:
C:\TEMP>kolikot [11,12,13,2,1,1] 230 181 C:\TEMP>kolikot [340,432,111,152,87,40] 2300 3988338 C:\TEMP>kolikot [4000,5000,4000,2800,2700,2400] 99800 268030896857300
(viimeiseen meni jo pari kolme minsaa, toinen on alle sekunnin)
Se herjaa heti, että "no parse" jos välilyöntejä jää tuonne listaan. Ja []-merkit pitää olla kanssa. Tiedoksi ihan siltä varalta, jos joku haluaa kokeilla. Anteeksi laiskuuteni. Se on meille haskellisteille ominaista...
Tässäpä sitten se koodi itse. Jätin häiritsevät kommentit ym. pois silkkaa ystävällisyyttäni.
import qualified Data.IntMap as IM
import System.Environment (getArgs)
main = do
(a:b:_) <- getArgs
let rajat = read a; kohde = read b in
print $ totaali rajat kohde
kolikot = [5,10,20,50,100,200]
mahdSummat kohdeLuku = [0,pienin..kohdeLuku]
where pienin = head kolikot
erotukset rajat = let maarat = map (enumFromTo 0) rajat in
zipWith (\k -> map (*k)) kolikot maarat
eiKolikoita kohdeLuku = IM.fromList $
zip (mahdSummat kohdeLuku) (1 : repeat 0)
edeltajat arvo = takeWhile (>=0) . map (arvo -)
seuraavaKolikko erotusLista edKolikko = let
uusiArvo vanha = sum . map (edKolikko IM.!) . edeltajat vanha
summaus paikka _ = uusiArvo paikka erotusLista
in IM.mapWithKey summaus edKolikko
toiseksiViimeinen rajat kohdeLuku = let
alku = eiKolikoita kohdeLuku
erot = init $ erotukset rajat
in foldr seuraavaKolikko alku erot
totaali rajat kohdeLuku = let
edellinen = toiseksiViimeinen rajat kohdeLuku
erotusLista = last $ erotukset rajat
paikat = edeltajat kohdeLuku erotusLista
in sum $ map (edellinen IM.!) paikatEi tämä ihan kauniisti suomeksi suju. Erottuupa kuitenkin omat määritelmät kielen termeistä selvemmin.
Aihe on jo aika vanha, joten et voi enää vastata siihen.