[JAVA] Munten Inruil Probleem

[Verwijderd]

Hoi,

Ik heb een probleempje in JAVA. Ik zal eerst eens het probleem nader toelichten.
Ik heb een muntensysteem, munten met de waardes 1,2,5,10,20 en 50. (Totaal 6 verschillende soorten munten). Nu wil ik het bedrag 28 zo gemakkelijk mogelijk betalen. Dus zo min mogelijk munten hoeven te geven, en zo min mogelijk munten hoeven te ontvangen. De uitkomst van het programma moet zijn, hoeveel munten van eigenaar verwisselt zijn. Zoals je onderaan al een stuk code ziet, deze code geeft mij de oplossing om het gemakkelijkste 19 te betalen, zonder dat ik iets terug krijg. De computer zou mij dan 10+5+2+2 geven. Alleen het kan sneller, want als ik ook nog geld terug krijg, zou het eenvoudiger kunnen 20-1. Hoe moet ik dit oplossen? Iemand een idee?

code:

class MuntenVb
{
    final int munten[] = {1, 2, 5, 10, 20, 50}, MAX = 6;
    
    public static void main(String args[])
    {
    MuntenVb prg = new MuntenVb();
    System.out.println("het minimum is " + prg.minmunt(19, 0));
    }


    int minmunt(int bedrag, int muntType)
    {
    int i, aantal, minimum;
    if (bedrag == 0)
        return 0;
    minimum = bedrag;
    for (i = muntType; i < MAX; i++)
        if (bedrag > munten[i])
        {
            aantal = bedrag / munten[i];
        aantal += minmunt(bedrag - (aantal * munten[i])+1, muntType + 1);
        if (aantal < minimum)
            minimum = aantal;
        }
    return minimum;
    }
}

Alvast Bedankt voor je hulp

[Infinitive]

Voor het muntwissel probleem zal op internet toch wel heel er veel...

Ik heb wat linkjes naar powerpoint files voor je, in een van de twee staat denk ik wel een voorbeeld dat je kan gebruiken (weet niet uit m'n hoofd welke ppt file):

http://www.cs.uu.nl/docs/vakken/al/algoritmiek2003-3.ppt
http://www.cs.uu.nl/docs/vakken/al/algoritmiek2003-4.ppt

Nog een opmerking:
Als je als truuck gebruikt dat je altijd met een zo groot mogelijke munt probeert te betalen, dan kom je mogelijk niet op een optimale oplossing uit, afhankelijk van de waarden van je munten. Met guldens en euro's kom je wel altijd goed uit heb ik gehoord.

edit: ik zie dat je als complicatie hebt dat je zelf misschien ook nog muntstukken gaat teruggeven. Dit maakt het al een stuk lastiger... hoewel, als je stelt dat de ander altijd minder mag teruggeven dan jij betaald, dan moet er wel uit te komen zijn.

[ Voor 47% gewijzigd door Infinitive op 07-01-2004 23:16 ]

[Soultaker]

Het lijkt me een typisch zoekprobleem. Nu zou dat in theorie erg ingewikkeld kunnen worden, maar gelukkig hoef je alleen maar de bedragen van -50 tot 50 te doorzoeken; daarboven (of onder) kun je gewoon munten van 50 (terug) geven, totdat je binnen het gewenste bereik zit.

edit:
Hmm, ik ben achteraf gezien niet zo zeker van die grens, maar ik weet wel zeker dat er een beperking aan het bereik zit dat je hoeft te precalculeren.

[ Voor 24% gewijzigd door Soultaker op 07-01-2004 23:12 ]

[Verwijderd]

Infinitive> Bedankt voor je links, ik zal er morgen eens naar kijken, in een vluchtige blik kwam ik wel wat handige dingentjes tegen! Ik heb zelf al wel zitten zoeken op Google etc. Maar dit heb ik daar niet gevonden!

SoulTaker> Je zou een bovengrens kunnen uitrekenen idd, maar het probleem is dat de code dan alleen voor dit muntenstelsel geschikt is. Als je nu een ander muntenstelsel wilt nemen bijvoorbeeld: 1,2.5,5,10,25,50,100 (van de gulden, eerder gebruikte voorbeeld was van de euro)

[The Eagle]

Klinkt als een praticum dat ik ooit eens op de Haagse Hogeschol heb moeten doen, alleen dat was in C. Geen idee hoe dat toen geprogd werd (had gelukkig een projectmaatje die WEL kon programmeren ) Maar ik weet idd wel dat je zo groot mogelijk terug moet geven. En ik weet ook dat er vast wel een routine voor te vinden zal zijn met Google.

[Infinitive]

Dit gaat een vrij nutteloze post worden ben ik bang, maar goed:

Ik bedacht me dat als je er vanuit gaat dat je tegenpartij ook geld terug mag geven en hij ook dezelfde soorten muntjes heeft en ook een oneindige hoeveelheid van elk, dat je dan via een truuckje met een recurrente betrekking wel een algoritme kan opschrijven.

Je gaat in principe alle mogelijkheden proberen: ik betaal 0 of meer maal munt i, de ander geeft 0 of meer maal munt j. Je doet dit voor alle munten en daar komt een bedrag uit rollen. Als dit 0 is tel je het aantal ontvangen en gegeven munten bij elkaar op en je kiest de mogelijkheid met minste aantal. Probleem is dat het aantal mogelijkheden op deze manier oneindig is: na enkele stappen kan je weer op de beginsituatie uitkomen.

De oplossing daarvoor is het limiteren van het bedrag dat je kan betalen en het bedrag dat je mag ontvangen. Door dit te limiteren op het initeële bedrag + totale waarde als je alle munten slechts eenmaal pakt, dan kan je met deze beperking toch nog een optimale oplossing bereiken (denk ik...). Nu heb je geen oneindig veel mogelijkheden meer en een oplossing is mogelijk.

Je krijgt alleen een recurrente betrekking met 5 parameters (2 munt-indices, het bedrag waar je nu op zit, en de twee totaal ontvang en geef parameters).

[Verwijderd]

Infinitive schreef op 07 januari 2004 @ 23:50:
De oplossing daarvoor is het limiteren van het bedrag dat je kan betalen en het bedrag dat je mag ontvangen. Door dit te limiteren op het initeële bedrag + totale waarde als je alle munten slechts eenmaal pakt, dan kan je met deze beperking toch nog een optimale oplossing bereiken (denk ik...). Nu heb je geen oneindig veel mogelijkheden meer en een oplossing is mogelijk..

Daar valt wat op te bedenken. Als je al die mogelijkheden tot 3 diep maakt. Want 4x1 = 2x2 dus hoef je niet verder dan 3 diep.
Dit probleem is ook een soort van opdracht. Daarbij geldt ook nog dat het maximale gevraagde bedrag maar 1000 kan zijn, en het maximale aantal soorten munten 15 kan zijn. Dat zou dus beteken 15P3 en dat is = 2730 mogelijkheden
Met wat leuke For loopjes zal dat wel lukken...

[Infinitive]

Ik heb in haskell mijn ideetje even verder uitgewerkt. Probleem is dat je waarschijnlijk de notatie van deze taal niet kent.

Met wat min of meer triviale transformaties is zo'n recursieve functie naar een programma in bijvoorbeeld java te vertalen. Nu berekent het bijvoorbeeld alleen de totaalwaarde: maar aangezien je kan achterhalen welk element je als minima hebt gekozen, kan je zo je algoritme uitbreiden om de oplossing te construeren.

Voor de liefhebbers zo'n functie in Haskell. Als ik aantalMunten 19 doet komt er twee uit. Merk op dat in deze vorm de functie heeel veel tijd kost...

code:

aantalMunten :: Int -> Int
aantalMunten initieelBedrag
  = m 6 6 initieelBedrag 0 0
  where
    m :: Int -> Int -> Int -> Int -> Int -> Int
    m _ _ 0 _ _ = 0
    m 0 _ _ _ _ = inf
    m _ 0 _ _ _ = inf
    m i j b tb to
      | max tb to > initieelBedrag + muntsum = inf
      | otherwise = minimum [ m (i-1) (j-1) b tb to             -- betaal geen munt i en ontvang geen munt j
                            , 1 + m i (j-1) (b - w i) (tb + w i) to   -- betaal munt i en ontvang geen munt j
                            , 1 + m (i-1) j (b + w j) tb (to + w j)   -- betaal geen munt i en ontvang munt j
                            ]

-- waarde van een muntje
w :: Int -> Int
w 1 = 1
w 2 = 2
w 3 = 5
w 4 = 10
w 5 = 20
w 6 = 50

muntsum = sum $ map w $ [1..6]

inf :: Int
inf = 32768 -- mwa, is toch best groot... :)

BTW: als je nog meer restricties gaat opleggen op betaling wordt op zich de functie niet spectaculair moeilijker: je termineerd alleen sneller executiepaden en in je code komt dat op wat meer voorwaarden neer.

edit: grappig, het bedrag 17 is een van de weinige onder de 20 die je niet met 2 muntjes kan betalen

[ Voor 13% gewijzigd door Infinitive op 08-01-2004 00:11 ]

[PipelineNoise]

Ik zou het zo doen:
Je neemt de waarde van de munt die direct boven het te betalen bedrag zit (in het geval van 19 is dat dus 20. Als het boven de 50 is, moet je ff wat maken dat je zo dicht mogelijk er boven zit). Daarna haal je 19 van 20 af, en bekijk je hoe je met zo min mogelijk munten '1' kan betalen (door weer de methode 'int minmunt' aan te roepen).
Bij het aantal munten dat je nodig hebt om '1' te betalen, tel je 1 op (voor de munt van 20, of natuurlijk meer als je boven de 50 zit).
Dan vergelijk je de uitkomst van het dirtect betalen (zonder teruggave) of met wisselgeld. De laagste uitkomst retourneer je.
Volgens mij moet dit werken!

[Voutloos]

Verwijderd schreef op 07 januari 2004 @ 23:56:
[...]


Daar valt wat op te bedenken. Als je al die mogelijkheden tot 3 diep maakt. Want 4x1 = 2x2 dus hoef je niet verder dan 3 diep.
Dit probleem is ook een soort van opdracht. Daarbij geldt ook nog dat het maximale gevraagde bedrag maar 1000 kan zijn, en het maximale aantal soorten munten 15 kan zijn. Dat zou dus beteken 15P3 en dat is = 2730 mogelijkheden
Met wat leuke For loopjes zal dat wel lukken...

Je kan in je code wat slimme if-jes bouwen.
Bijvoorbeeld:
Als het gevraagde bedrag eindigd op 0,2,4 of 8, heeft het _nooit_ zin om met oneven munten te betalen, danwel terug te kunnen gegeven.
6 is uitzondering want dan is 5+1 het kortst.
Maar dat is ook een snellere methode, want dan leg je 5 en 1 al vast.
Indien eindcijfer 6, kan je dus meteen 5+1 kiezen en de rest met 10/20/50 doen.

Etc...

Een paar keer zulke checks inbouwen en je bespaart heel veel rekenwerk.

Je mag ook mogelijkheden weg laten want de vraag is puur het minimale aantal muntjes, niet op hoeveel manieren je dat kan.

Nog een besparing: Een muntsoort dat betaald wordt, moet je nooit teruggeven, want dan kan je nooit de kortste route hebben.

Eitje.

[ Voor 16% gewijzigd door Voutloos op 08-01-2004 00:18 ]

[RickN]

Volgens mij kun je dit probleem opschrijven als een soort knapzak probleem.

-Het te betalen bedrag is de capaciteit (volume) van de knapzak.
-Je "voorwerpen" zijn alle muntsoorten én al die munten maar dan met een negatieve waarde. (Hiermee modeleer je het terugkrijgen van geld). Alle voorwerpen zijn onbeperkt beschikbaar.
-Het volume van een voorwerp is de waarde van de munt. (Tricky, want kan dus ook negatief zijn)
-De waarde van alle voorwerpen is 1.

Je wilt nu het aantal voorwerpen in de zak minimaliseren (de waarde), maar ook afdwingen dat de knapzak helemaal gevuld wordt. Dit kun je wel in een kostenfunctie vangen, door aan niet gevulde capaciteit een hele hoge waarde te verbinden.

Onder bepaalde condities (iig integer argumenten) kun je het knapzak probleem in polynomiale tijd oplossen, maar ik doorzie zo gauw niet of dat met negatieve volumes en de wat afwijkende kostenfunctie ook zo is.

[ Voor 15% gewijzigd door RickN op 08-01-2004 09:55 ]

[Grijze Vos]

RickN schreef op 08 januari 2004 @ 09:40:
Onder bepaalde condities (iig integer argumenten) kun je het knapzak probleem in polynomiale tijd oplossen, maar ik doorzie zo gauw niet of dat met negatieve volumes en de wat afwijkende kostenfunctie ook zo is.

Wat versta je onder 'polynomiale tijd'?

Ik vind namelijk een verschil tussen x^2 en x^10 niet onbelangrijk

[Infinitive]

Met het ding waar ik het over had, als je daar een polynominale versie van maakt, dan zit je aan minstens n^5, waarbij n het bedrag is. Maar dat gebruikte een algemene aanpak van het probleem, waarbij maar weinig analyse van het specifieke probleem zelf gebruikt wordt. Er zullen vast betere en ook optimale oplossingen voor zijn. Maar als een optimale oplossing zoveel rekentijd kost, dan ga je liever voor een benaderingsaanpak die veel sneller is en voor practische doeleinden hooguit een muntje extra te betalen opleverd.

Dit zijn natuurlijk wel typische problemen. Het zou me niets verbazen of voor de hele familie van muntwisselproblemen allerlei materiaal op internet te vinden is.

[Soultaker]

Als je begint met een vector van muntwaarden (in het voorbeeld [ 1, 2, 5, 10, 20, 50 ] ) dan is de oplossing een vector die per munt het aantal aangeeft dat je geeft (of ontvangt), waarbij het inproduct met de muntwaarden gelijk moet zijn aan het doelbedrag. Voor een doelbedrag van 19 is de optimale oplossing bijvoorbeeld [ -1, 0, 0, 0, 1, 0 ] (je geeft een munt van 20 en je krijgt er een van 1 terug).

In theorie is kan die vector elke mogelijke waarde aannemen maar als je het totale aantal muntwisselingen (oftewel de som van de absolute componenten van de vector) moet minimaliseren, kun je al meer beperkingen toevoegen. Je hoeft met een bepaalde munt namelijk nooit een bedrag te betalen dat ook te betalen is met hogere muntwaarden; het heeft bijvoorbeeld geen zin om twee of meer munten van 1 te geven (of terug te ontvangen), want je kan dan beter eerst een paar munten van 2 geven. Hetzelfde geld voor munten van 2: voor vijf munten van 2 kun je ook twee munten van 5 geven. Op die manier krijg je dus per component een (absoluut) maximum: [ 2, 5, 2, 2, 5, - ]. Alleen voor de laatste component is het aantal onbepaald, maar gelukkig ligt de waarde daarvan vast als je de overige componenten gekozen hebt. Je hoeft in dit voorbeeld dus maar 3*9*3*3 = 243 iteraties uit te voeren om uit te zoeken hoe je een willekeurig groot bedrag optimaal betaald. (Per component heb je namelijk 2*MAX-1 mogelijkheden, aangezien het aantal zowel positief als negatief kan zijn, maar je de 0 niet dubbel moet tellen.)

Overigens vermoed ik dat dit een bovengrens is; ik kan me voorstellen dat het ook niet nodig is om (bijvoorbeeld) drie munten van 2 te geven, want dan kan je immers beter een munt van 5 en een munt van 1 geven. Dat beïnvloed echter de beslissing dat je nooit meer dan een munt van 1 hoeft te geven (dat kan dan toch mogelijk zijn) en dan wordt het uitzoeken van de maxima dus wat ingewikkelder (maar heb je als voordeel een minder groot domein van de waarden in je oplossingsvector).

De 'simpele' maxima die ik beschreef zijn simpel te vinden door voor elke component het kleinste gemene veelvoud met elke grotere component te vinden; de minimale waarde daarvan is het minimale bedrag dat niet meer met die munt betaald hoeft te worden (en aantal munten is dus gelijk aan dat bedrag gedeeld door de waarde van de munt).

[Soultaker]

PipelineNoise schreef op 08 januari 2004 @ 00:07:
Ik zou het zo doen:
Je neemt de waarde van de munt die direct boven het te betalen bedrag zit (in het geval van 19 is dat dus 20.

Dat is veel te simpel. Als je bijvoorbeeld als munten 1, 3, 7 en 8 hebt, en je moet 5 maken, dan is de optimale oplossing 8 - 3 en dan begin je dus niet bij 3 of 7 (de bedragen die er het dichtst bij liggen).

[Voutloos]

Soultaker schreef op 08 januari 2004 @ 11:12:
[...]

Dat is veel te simpel. Als je bijvoorbeeld als munten 1, 3, 7 en 8 hebt, en je moet 5 maken, dan is de optimale oplossing 8 - 3 en dan begin je dus niet bij 3 of 7 (de bedragen die er het dichtst bij liggen).

Indien de muntjes vastliggen zoals TS ze stelt, vind ik mijn oplossing mooi.
indien de muntjes variabel zijn, is er vast wel een algoritme te maken die voor bepaalde eindcijfers etc de branchmogelijkheden beperkt. Echter moet het stelsel dan wel regelmatig zijn. Bij stelsel zoals Soultaker die nu geeft wordt dat al wat lastiger. (Maar is met veel modulo berekeningen ook te doen)

Eigenlijk zitten jullie meer aan algemene AI zoektechnieken te denken, terwijl ik juist eerder naar slimme methodes kijk om het aantal mogelijkheden in te perken. Allebei is natuurlijk een aanpak, alhoewel ik niet weet welke kant TS op wil.

[Soultaker]

Voutloos schreef op 08 januari 2004 @ 12:20:
Eigenlijk zitten jullie meer aan algemene AI zoektechnieken te denken, terwijl ik juist eerder naar slimme methodes kijk om het aantal mogelijkheden in te perken. Allebei is natuurlijk een aanpak, alhoewel ik niet weet welke kant TS op wil.

Slim zoeken is de mogelijkheden beperken. Het probleem met jouw "slimme methodes" vind ik dat ze niet algemeen toepasbaar zijn. Je gaf al een voorbeeld dat in een specifiek geval zou kunnen werken en daarna gaf je zelf alweer een uitzondering. Als je niet kunt garanderen dat je methode altijd de goede oplossing geeft, dan heb je niet zoveel aan slimmigheden, lijkt me.

Overigens ging mijn methode ook juist uit van het beperken van de zoekruimte. Voor de voorbeelden van de topic starter ligt de zoekruimte rond de 2000 gevallen; dat lijkt me al best aardig.

[Verwijderd]

Hier heb ik een mooie heuristiek voor geleerd. Mijn cursus daarvan ligt thuis, maar ik kan het in het weekend altijd eens opzoeken als je dat wilt.

[RickN]

Ik heb nog ff na zitten denken.

Conclusie: Het algemene probleem, d.w.z. met een arbitrair aantal verschillende munten van arbitraire waarde (wel integer) is een "integer linear programming problem" en dus NP-compleet.

[ Voor 16% gewijzigd door RickN op 08-01-2004 15:09 ]

[Erik Jan]

[rml][ alg] Algoritme: veel albums op weinig cd's *[/rml]

Toevallig las ik een paar dagen geleden dit oude, maar relevante topic. Misschien dat het iets bijdraagt. Volgens mij komt het erop neer dat, wanneer je steeds de perfecte oplossing zoekt, je uren bezig bent met rekenen. Als je genoegen neemt met een benaderde oplossing, kan je in enkele seconden klaar zijn.

Verder stijgt dit boven mijn magere wiskunde-b1,2 pet

[staefke]

Eej,

heb het ff uitgeprogrammeerd (in C++ welliswaar), waarin het idee ongeveer als volgt is:

je moet het aantal munt transacties minimaliseren, dit wordt weergegeven in een lijst van integers, met positieve getallen voor datgene wat je betaalt, en negatieve getallen voor wat je terugkrijgt. De lengte van deze lijst is het aantal munttransacties.

Aangezien het aantal bedragen beperkt is, kun je dit best ff voor alle bedragen doen, maar volgens mij moet je het maximum bedrag ook wel kunnen afleiden uit de verhouding van het ingegeven getal en de grootste munteenheid...(nog niet naar gekeken maar het onderbuik gevoel zegt dat er wel iets over af te leiden valt... das voor een andere keer).

Dus maak je een array/vector aan voor alle bedragen met daarin een lijst van alle munten die voor dat bedrag op dat moment bepaald zijn. Daarvoor moet het array ff op een goeie wijze geinitialiseerd worden:

Het idee is dan als volgt:
1. vul eerst het array met de bedragen die gelijk zijn aan de munteenheden (let wel, we hebben het hier alleen over munten met integer waarden, dus voor een knaak werkt het niet, aangezien de muntwaarden als indices in dit array worden gebruikt).

2. Ga vanuit die waarden opzoek naar andere waarden die gelijk zijn aan de reeds gevonden waarden (in eerste instantie zijn dit de munteengeden) plus de waardes van de afzonderlijke munteenheden... volgt u het nog ? Als de voorgestelde lijst met munten korter is dan de reeds gevonden lijst met munten, vervang hem dan...

itereer dit tot er geen veranderingen meer hebben plaats gevonden...

nu zijn er natuurlijk een aantal implementatie issues (ga niet zeiken over stijl aub, heb dit ff een keer niet braaf opgelost met iterators en design patterns etc...) zoals een init variabele met een lengte 100 wat ervoor zorgt dat de vergelijking van de lengte van de lijst ff ook de eerste keer (als er voor een bedrag nog geen lijst is afgeleid) klopt.

voorbeeld:

munten 1 2 5 10
max amount op 10

* initialisatie...

datastructuur amounts
1 {1}
2 {2}
3 {0, 0, 0, 0, ...}
4 {0, 0, 0, 0, ...
5 {5}
6 {0, 0, 0, 0, ...}
7 {0, 0, 0, 0, ...}
8 {0, 0, 0, 0, ...}
9 {0, 0, 0, 0, ...}
10 {10}

daarna wordt de zaak geupdate...

dus vanuit het bedrag 2 vinden we
1 : (door (2, -1) maar dat is langer dan (1) -> gaat niet door)
3 : (2, 1) -> das korter dan de init lijst dus die nemen we over...
4 : (2, 2) -> idem
7 : 2, 5 -> idem

en zo doe je dat voor al die bedragen...voila...

run anders fragment van onderstaand programmaatje maar ff....
(check ff includes en namespaces enzo......)

moet volgens mij niet zo moeilijk zijn om dit ff naar Java te porten...

code:

#define MAX 100
#define NR_COINS 7
int g_coins[NR_COINS] = {1,2,5,10,20, 100};

void pay(int n)
{
    int i, j;
    std::vector<std::vector<int> > amounts(MAX + 1);
    
    std::vector<int> init(100);
    for ( i = 1; i <= MAX ; ++i)
        amounts[i] = init;
    
    /* init */
    for (i=0; i < NR_COINS; ++i)
    {
        std::vector<int> temp; temp.push_back(g_coins[i]);
        amounts[g_coins[i]] = temp;
    }

    int new_amount, nCount = 0;
    bool bModified = true;
    while(bModified)
    {
        ++nCount;
        cout << "round " << nCount << endl;
        bModified = false;
        for (i = 1 ; i <= MAX ; ++i)
        {
            int amount_size = amounts[i].size();
            if (amount_size != 0)
            {
                for ( j = 0; j < NR_COINS; ++j)
                {
                    new_amount = i + g_coins[j];
                    if ( new_amount <= MAX)
                    {
                        if (amounts[new_amount].size() > amount_size + 1)
                        {
                            amounts[new_amount] = amounts[i];
                            amounts[new_amount].push_back(g_coins[j]);
                            bModified = true;
                        }
                    }
                    new_amount = i - g_coins[j];
                    if (new_amount  > 0)
                    {
                        if (amounts[new_amount].size() > amount_size + 1)
                        {
                            amounts[new_amount] = amounts[i];
                            amounts[new_amount].push_back(-1 * g_coins[j]);
                            bModified = true;
                        }
                    }
                }
            }
        }
    }


    for (i = 1 ; i <= MAX ; ++i)
    {
        cout << i << " : ";
        for (j = 0; j < amounts[i].size(); ++j)
            cout << amounts[i][j] << " ";
        cout << endl;
    }
}

voorbeeld output voor munten 1,2,5,10,20,100

code:

84
round 1
round 2
round 3
round 4
1 : 1
2 : 2
3 : 1 2
4 : 2 2
5 : 5
6 : 1 5
7 : 2 5
8 : 10 -2
9 : 10 -1
10 : 10
11 : 1 10
12 : 2 10
13 : 1 2 10
14 : 2 2 10
15 : 5 10
16 : 1 5 10
17 : 2 5 10
18 : 20 -2
19 : 20 -1
20 : 20
21 : 1 20
22 : 2 20
23 : 1 2 20
24 : 2 2 20
25 : 5 20
26 : 1 5 20
27 : 2 5 20
28 : 10 20 -2
29 : 10 20 -1
30 : 10 20
31 : 1 10 20
32 : 2 10 20
33 : 1 2 10 20
34 : 2 2 10 20
35 : 5 10 20
36 : 1 5 10 20
37 : 2 5 10 20
38 : 20 20 -2
39 : 20 20 -1
40 : 20 20
41 : 1 20 20
42 : 2 20 20
43 : 1 2 20 20
44 : 2 2 20 20
45 : 5 20 20
46 : 1 5 20 20
47 : 2 5 20 20
48 : 10 20 20 -2
49 : 10 20 20 -1
50 : 10 20 20
51 : 1 10 20 20
52 : 2 10 20 20
53 : 1 2 10 20 20
54 : 2 2 10 20 20
55 : 5 10 20 20
56 : 1 5 10 20 20
57 : 2 5 10 20 20
58 : 20 20 20 -2
59 : 20 20 20 -1
60 : 20 20 20
61 : 1 20 20 20
62 : 2 20 20 20
63 : 1 2 20 20 20
64 : 2 2 20 20 20
65 : 5 20 20 20
66 : 1 5 20 20 20
67 : 2 5 20 20 20
68 : 100 -20 -10 -2
69 : 100 -20 -10 -1
70 : 100 -20 -10
71 : 100 -20 1 -10
72 : 100 -20 2 -10
73 : 100 -20 -5 -2
74 : 100 -20 -5 -1
75 : 100 -20 -5
76 : 100 -20 1 -5
77 : 100 -20 2 -5
78 : 100 -20 -2
79 : 100 -20 -1
80 : 100 -20
81 : 100 -20 1
82 : 100 -20 2
83 : 100 -20 1 2
84 : 100 -20 2 2
85 : 100 -20 5
86 : 100 -20 1 5
87 : 100 -20 2 5
88 : 100 -10 -2
89 : 100 -10 -1
90 : 100 -10
91 : 100 -10 1
92 : 100 -10 2
93 : 100 -5 -2
94 : 100 -5 -1
95 : 100 -5
96 : 100 -5 1
97 : 100 -5 2
98 : 100 -2
99 : 100 -1
100 : 100
Press any key to continue

Hoop dat je der wat aan hebt,
mazzels,
Staefke

[Verwijderd]

Hartelijk dank iedereen.
staefke> Jouw C++ gedoe, ben ik nu aan het omzetten naar JAVA. Alleen stoot ik op de functie size(), ik weet niet wat ie doet. En de functie, push_back() waarmee je iets achteraan een int zet, maar welke funcite in JAVA daarvoor gebruikt wordt??

[staefke]

size() geeft de lengte weer van de vector weer (kan dus variabel zijn)... Volgens mij is dat zoiets als een length() member van een collection class uit JAVA...
In dit geval geeft de size dus de lengte weer van alle benodigde munten voor een bepaald bedrag...

wat betreft het push_back gebeuren, je zou hier volgens mij (ff uit mn hoofd) een ArrayList voor kunnen gebruiken, of sowieso een List achtige container, die moet altijd iets hebben om een element achteraan de lijst te kunnen plakken.. .

dat push_back() wordt alleen uitgevoerd op de afzonderlijke munten voor een bepaald bedrag, hier heb je sowieso geen indexering nodig.... dus een of andere list zou voldoende moeten zijn...

[Soultaker]

Ik heb desgewenst nog een alternatieve implementatie die in complexiteit alleen afhankelijk is van verzameling munten (en dus niet van de grootte van het te betalen bedrag).

Staefke's oplossing is wel aardig, maar ik heb het idee dat de complexiteit bij grotere invoer nogal uit de klauwen kan lopen. Ik heb het idee dat het een variatie is op de oplossing zonder het teruggeven van geld, die namelijk wel netjes met dynamisch programmeren opgelost kan worden.

[drm]

Kolky_nl:
Hartelijk dank iedereen.
staefke> Jouw C++ gedoe, ben ik nu aan het omzetten naar JAVA. Alleen stoot ik op de functie size(), ik weet niet wat ie doet.

Wat zou een size() methode nou teruggeven bij een vector...?

En de functie, push_back() waarmee je iets achteraan een int zet, maar welke funcite in JAVA daarvoor gebruikt wordt??

Volgens mij moet je dit gewoon even doorlezen.

Als je dat al niet zelf uit kan vinden vraag ik me uberhaupt af of je het algoritme van staefke wel begrijpt...

[staefke]

Soultaker schreef op 08 januari 2004 @ 19:28:
Ik heb desgewenst nog een alternatieve implementatie die in complexiteit alleen afhankelijk is van verzameling munten (en dus niet van de grootte van het te betalen bedrag).

Staefke's oplossing is wel aardig, maar ik heb het idee dat de complexiteit bij grotere invoer nogal uit de klauwen kan lopen. Ik heb het idee dat het een variatie is op de oplossing zonder het teruggeven van geld, die namelijk wel netjes met dynamisch programmeren opgelost kan worden.

nouja... afgezien van het geheugen gebruik...
Het teruggeven van geld zorgt er wel voor dat de zoekruimte een stuk ruimer wordt..

maar heb zelf ook wel het idee dat hier een graafje maken met als knooppunten al die bedragen met daartussen wat munttransacties en een opgeleukt (misschien wel kortste-) pad algoritme het nog wat beter kan doen, want in dat algoritme van mij is elke oplossing gebaseerd op een suboplossing. Stel dat voor een bedrag (dat ook als basis dient voor een ander bedrag) een betere oplossing wordt gevonden, dan moeten alle afhankelijke oplossingen nu nog eens worden geevalueerd, terwijl je dat in een graaf zo kunt programmeren dat je dat kado krijgt...

ik wil die alternatieve implementatie wel es zien waar het alleen van de munten afhangt...

[Norjee]

Laat ik mijn oplossing ook maar posten

Hij is lomp, maar werkt wel.

Om "terug betalen" gedaan te krijgen heb ik negatieve muntjes.

Wat ik nu doe? Een boom doorlopen.

code:

stap 1   stap 2
===============

         1     
1---\    2     
     \-- 5    
               
         1     
2        2     
         5     
               
         1     
5        2     
         5

Van het begin bedrag wordt bij elke stap in de boom die waarde hiervan afgetrokken, tot je nul overhoud.

Java:

import java.util.Vector;

public class Muntjes
    {
    private static int[] waarden = {1, 2, 5, 10, 20, 50, -50, -20, -10, -5, -2, -1};
    private static int currentStappen = 50;

    public static void main(String[] args)
        {
        int waarde = Integer.parseInt(args[0]);

        loopDoorPaden(waarde, 0, new Vector());


        }

    private static void loopDoorPaden(int waarde, int stappen, Vector muntjes)
        {
        if (stappen < currentStappen)
            {
            int maxPaden = waarden.length;
            int rest = 0;
            for (int i = 0; i < maxPaden; i++)
                {
                Vector currentMuntjes = (Vector) muntjes.clone();
                rest = getRest(waarde, i, currentMuntjes);
                if (rest == 0)
                    {
                    currentStappen = stappen + 1;
                    printFound(currentStappen, currentMuntjes);
                    }
                else
                    {
                    loopDoorPaden(rest, 1 + stappen, currentMuntjes);
                    }
                }
            }
        }

    private static int getRest(int rest, int pad, Vector muntjes)
        {
        muntjes.add(new Integer(waarden[pad]));
        return rest - waarden[pad];
        }

    private static void printFound(int stappen, Vector muntjes)
        {
        System.out.println(stappen + " stappen:");
        for (int i = 0; i < muntjes.size(); i++)
            {
            Integer muntje = (Integer) muntjes.elementAt(i);
            System.out.print(muntje.toString() + " ");
            }
        System.out.println("");
        System.out.println("");

        }
    }

Maar eigenlijk wil je dit niet op deze manier oplossen, want het zijn nodeloos veel iteraties.

[ Voor 3% gewijzigd door Norjee op 08-01-2004 23:54 ]

[RTBravo]

Dit lijkt wel verdacht veel op het projectje dat ik in het eerste semester hogere informatica moest doen De geldwisselautomaat! Of heb je een andere reden waarom je dit wilt weten? Huiswerkvragen mochten toch niet gepost worden?

[Macros]

RTBravo schreef op 08 januari 2004 @ 23:56:
Dit lijkt wel verdacht veel op het projectje dat ik in het eerste semester hogere informatica moest doen De geldwisselautomaat! Of heb je een andere reden waarom je dit wilt weten? Huiswerkvragen mochten toch niet gepost worden?

Omdat NP-complete problemen cool zijn!

[drm]

Huiswerkvragen mochten toch niet gepost worden?

Als het niet had gemogen dan was 't bij de topicstart al dicht gegaan, want toen was ook al wel duidelijk _{klein beetje maar, hoor} dat het een schoolopdracht was

[Soultaker]

staefke schreef op 08 januari 2004 @ 22:10:
ik wil die alternatieve implementatie wel es zien waar het alleen van de munten afhangt...

Sorry voor de grote lap code, maar er zit wat debug-info enzo tussen:

edit:
Uit concurrentieoverwegingen de code even verwijderd; (zie de reactie van Mountainman).

[ Voor 79% gewijzigd door Soultaker op 09-01-2004 13:33 ]

[staefke]

mooie oplossing Soul

btw, als iemand van dit soort probleempjes plus oplossingen enzo houdt, kijk dan ff op www.topcoder.com, hebben ze allemaal van dit soort stuff...

toedels,
Staefke

[Mountainman]

Dit is een opdracht voor de Nederlandse informatica olympiade... Dit is niet echt eerlijk voor je mede concurrenten denk ik

[staefke]

mogen wij dan ook meedoen

[Soultaker]

staefke schreef op 09 januari 2004 @ 12:35:
mogen wij dan ook meedoen

Als je op de middelbare school zit wel.

[Verwijderd]

Hey..

Het is / was idd voor de Informatica Olympiade. Mijn zeg maar laatste red middel. Ikzelf kwam er niet aan uit. Bovendien is vandaag de inleverdatum. Ik zal nix inleveren. Toch bedankt, ben van plan volgend jaar Informatica te gaan studeren... zodat ik het lekker zelf kan...

Topic mag gesloten worden hoor!

*EDIT: voor de geinterreseerd op de Academie voor ICT en Managment in Breda!

[ Voor 11% gewijzigd door Verwijderd op 10-01-2004 00:57 ]