---

Hvis man skulle implementere en tilbagebetalingsenhed til en automat
kunne man være interesseret i altic at tilbagebetale beløbet med så få
mønter som muligt.
For nemheds skyld kan vi regne i hele beløb og antage at automaten har
ubegrænset lager af tilbagebetalingsmønter i alle eksisterende
størrelser.

En naiv grådig algoritme kunne være, at man, sålænge man manglede at
betale noget, tilbagebetalte den største mønt der ikke er større end
restbeløbet.
Denne algoritme virker med vores møntsystem. Skal man f.eks.
tilbagebetale 14 kr vil automaten først spytte en 10'er og derefter to
2-ere ud.
Med mere sofisikerede møntsystemer virker algoritmen ikke. Havde vi
f.eks. også en 7-krone-mønt, ville den skitserede algoritme stadig
udbetale en 10'er og to 2'ere - men det optimale ville være to 7'ere.

Spørgsmål 1:
Er der nogen her, der er i stand til at opstille et simpelt sæt regler
som et system af mønter skal overholde for at den grådige algoritme
virker? Som sagt regner vi kun i hele beløb, og vi kan antage at
møntsystemet er konstrueret så alle beløb kan tilbagebetales - dvs. at
der findes en 1-krone-mønt.

Spørgsmål 2:
Findes en algoritme, der altid virker, og som har pladsforbrug O(antal
mønter * log(beløb)) og tidsforbrug O(beløb)?
( O(beløb+antal mønter) kan implementeres med simpel dynamisk
programmering )

-Rune

---

Rune Zedeler <rz@daimi.au.dk> skrev i artiklen
<3C038E35.D2DB368@daimi.au.dk>...
> Er der nogen her, der er i stand til at opstille et simpelt sæt regler
> som et system af mønter skal overholde for at den grådige algoritme
> virker?

Jeg ville lave et system, hvor jeg opstillede alle tænkelige kombinationer
af mønter, der havde en samlet beløbssum, der var mindre end restbeløbet.
Efterfølgende ville jeg så sortere dem efter, hvor mange mønter, der indgik
i hver kombination.

Jeg ville starte oppefra, sådan at jeg startede med kombinationer af så
mange store mønter som muligt. Første gang, jeg så stødte på en
kombination, der havde færre mønter end den foregående "rekordindehaver",
ville jeg udvælge denne.

---

"Christian R. Larsen" wrote:

> > Er der nogen her, der er i stand til at opstille et simpelt sæt regler
> > som et system af mønter skal overholde for at den grådige algoritme
> > virker?
>
> Jeg ville lave et system, hvor jeg opstillede alle tænkelige kombinationer
> af mønter, der havde en samlet beløbssum, der var mindre end restbeløbet.
> Efterfølgende ville jeg så sortere dem efter, hvor mange mønter, der indgik
> i hver kombination.
>
> Jeg ville starte oppefra, sådan at jeg startede med kombinationer af så
> mange store mønter som muligt. Første gang, jeg så stødte på en
> kombination, der havde færre mønter end den foregående "rekordindehaver",
> ville jeg udvælge denne.

Så vidt jeg kan se, snakker du om en algoritme til tilbagebetaling,
selvom det ikke er det spørgsmål, du har citeret.
Well, din algoritme vil være for langsom. Kan ikke overskue
tidskompleksiteten, men noget i retning af O((antal mønter)*(beløb)).

-Rune

---

Rune Zedeler <rz@daimi.au.dk> skrev i artiklen
<3C039844.E2C83E2B@daimi.au.dk>...
> Så vidt jeg kan se, snakker du om en algoritme til tilbagebetaling,
> selvom det ikke er det spørgsmål, du har citeret.

Rigtigt.

> Well, din algoritme vil være for langsom. Kan ikke overskue
> tidskompleksiteten, men noget i retning af O((antal mønter)*(beløb)).

Jeg tvivler på, at det bliver det store, vilde problem med hastigheden. I
realiteten kan man vel ikke forestille sig tilbagebetaling af beløb, der er
større end den største seddel.

---

"Christian R. Larsen" wrote:

> Jeg tvivler på, at det bliver det store, vilde problem med hastigheden. I
> realiteten kan man vel ikke forestille sig tilbagebetaling af beløb, der er
> større end den største seddel.

Nej, men algoritmen kan også finde anvendelse inden for andre
optimeringsområder end tilbagebetaling af mønter - og nogle af disse
arbejder med væsentligt større tal end sodavandsautomater.
I øvrigt skrev jeg direkte i mit første indlæg at jeg allerede havde
løst det konkrete problem - men for sjov skyld ledte efter en mere
optimal løsning (well, "for sjov"-delen skrev jeg ikke i det oprindelige
indlæg, well).
Hvis man ikke har noget imod pladsforbrug på (antal mønter)*(beløb) kan
man løse probemet dynamisk ved for hvert beløb (!) at lave en tabel over
hvilke mønter dette beløb skal udbetales i. Det jeg skrev i første
indlæg om plads- og tidsforbruget af den dynamiske algoritme holder vist
ikke.

-Rune

---

Rune Zedeler <rz@daimi.au.dk> skrev i artiklen
<3C03AA0D.F9876E33@daimi.au.dk>...
> Hvis man ikke har noget imod pladsforbrug på (antal mønter)*(beløb) kan
> man løse probemet dynamisk ved for hvert beløb (!) at lave en tabel over
> hvilke mønter dette beløb skal udbetales i. Det jeg skrev i første
> indlæg om plads- og tidsforbruget af den dynamiske algoritme holder vist
> ikke.

Ja, dette er jo den klassiske optimeringsmetode, som mange programmører vel
på et eller andet tidspunkt kommer ud for at skulle anvende.

---

Rune Zedeler <rz@daimi.au.dk> writes:

> Er der nogen her, der er i stand til at opstille et simpelt sæt
> regler som et system af mønter skal overholde for at den grådige
> algoritme virker?

Så vidt jeg lige kan overskue må det her induktive regelsæt virke:

M1 = 1
Mn >= 2*M(n-1) for alle n > 1.

Algoritmen der altid virker kan jeg til gengæld ikke lige overskue :)

- Kvan.

---

Kvan wrote:

> Så vidt jeg lige kan overskue må det her induktive regelsæt virke:
>
> M1 = 1
> Mn >= 2*M(n-1) for alle n > 1.
>
> Algoritmen der altid virker kan jeg til gengæld ikke lige overskue :)

Nope. Din betingelse er hverken nødvendig eller tilstrækkelig.

1,2,3,4,5 virker.
1,7,15 virker ikke (21 kroner, f.eks.).

-Rune

---

Rune Zedeler <rz@daimi.au.dk> writes:

> 1,2,3,4,5 virker.
> 1,7,15 virker ikke (21 kroner, f.eks.).

Hmm jeg kan ikke løse problemet, men jeg kan formalisere det lidt. I
det ovenstående eksempel kan vi indføre prisvariable p1=1, p2=7 og p3
=15 og antalsvariablene n1, n2 og n3. Tilbagebetalingen er givet ved

beløb = p1 * n1 + p2 * n2 + p3 * n3
= n1 + 7 * n2 + 15 n3

Hvis tilbagebetalingen skal være optimal må det gælde at

n1 < 7 (for ellers er det bedre at bruge en 7 krone)
n1 < 8 eller n7 < 1 (for ellers er det bedre at bruge en 15 krone)
n1 < 1 eller n7 < 2 (for ellers er det bedre at bruge en 15 krone)

Det burde være rimeligt let at finde på en datastruktur hvor man kan
lagre sådan nogle uligheder. Derefter burde det gå noget hurtigere når
man fyrede sine for-løkker af.

Jeg fandt to artikler om "Exact Analysis of Exact Change", men idag er
dagen hvor jeg skriver alle mine artikler ind i bibtex og jeg er lidt
bagud i forhold til tidsplanen, så jeg har ikke kigget dem igennem.
http://citeseer.nj.nec.com/context/127543/33166
http://citeseer.nj.nec.com/chan98easy.html

PS: Tak for sidst det var hyggeligt. Jeg har ikke helt fået styr på
farveprinteren endnu, men jeg har fundet ud af at ændre farvepalletten
med gimp, så det kan ikke gå helt galt.

--
Niels L Ellegaard http://dirac.ruc.dk/~gnalle/
SPECIAL OFFER! I proofread unsolicited commercial email sent to this
address at a rate of US $500.00 per incident! Include billing address
in your message and save US $500.00 per hour off ordinary address
resolution and tracking charge!

---

> Spørgsmål 2:
> Findes en algoritme, der altid virker, og som har pladsforbrug O(antal
> mønter * log(beløb)) og tidsforbrug O(beløb)?
> ( O(beløb+antal mønter) kan implementeres med simpel dynamisk
> programmering )

Da "antal mønter" < "max beløb" må der gælde at:
O(beløb+antal mønter) = O(beløb)

---

Thomas Krog wrote:

> Da "antal mønter" < "max beløb" må der gælde at:
> O(beløb+antal mønter) = O(beløb)

Undskyld, mit ordvalg er upræcist.
Med "antal mønter" mener jeg ikke "antal udbetalte mønter" men derimod
"antal forskellige mønter i møntsystemet".
Et værre problem er, at den dynamiske algoritme desværre afaics vil
kræve mere plads (antal mønter * beløb) - og at det, jeg skrev, derfor
var forkert.

-Rune

---

"Rune Zedeler" <rz@daimi.au.dk> wrote in message
news:3C038E35.D2DB368@daimi.au.dk...

> Spørgsmål 1:
> Er der nogen her, der er i stand til at opstille et simpelt sæt regler
> som et system af mønter skal overholde for at den grådige algoritme
> virker? Som sagt regner vi kun i hele beløb, og vi kan antage at
> møntsystemet er konstrueret så alle beløb kan tilbagebetales - dvs. at
> der findes en 1-krone-mønt.

Jeg hørte, at der var nogen der benyttede L^3-algoritmen (lattice reduction
af Lenstra, Lenstra og Lovasz) i en kasseautomat. Lidt overkill måske, men
sjovt nok.

For info om LLL, check f.eks.
http://www.cecm.sfu.ca/projects/IntegerRelations/LLL.html .

> Spørgsmål 2:
> Findes en algoritme, der altid virker, og som har pladsforbrug O(antal
> mønter * log(beløb)) og tidsforbrug O(beløb)?
> ( O(beløb+antal mønter) kan implementeres med simpel dynamisk
> programmering )

Check litteraturen om lattice reduction og L^3-algoritmen (eller LLL). Den
er også blevet brugt til at bryde knapsack-problemer, der var benyttet som
envejsfunktioner (til kryptosystemer).

Thomas