Milyen algoritmussal tudom meg, hogy legkevesebb hány, és milyen papírpénzzel tehető ki egy adott érték?

pl. van a 100

akkor osszeg = 50

ha osszeg + 50 == 100, akkor állj, ha nagyobb akkor ugrik a 20-asra, ha nem akkor hozzá add még 50-et

különben osszeg + 20 == 100, akkor állj, ha nagyobb akkor ugrik a 10-esre, ha nem akkor hozzá add még 20-at-et

szerintem így kéne

remélem jól értettem a feladatott

int price = 1345;

int banknote[5] = {50, 20, 10, 5, 1};

int result[5];

for (int i = 0; i < 5; i++)

{

result[i] = price / banknote[i];

price -= result[i] * banknote[i];

}

Kimenet:

result 0x0030f670 {26, 2, 0, 1, 0} int[5]

Az a probléma a fentebb említett algoritmusokkal hogy ha nem a "standard" 50, 20, 10 ,5 ,1 bankjegyekről beszélünk, akkor nem fog működni.

Például legyen az összeg 7, a bankjegyek pedig 5,4,3,1.

Ekkor ha legnagyobbtól indulunk a legkisebb felé, 5+1+1 fog kialakulni, pedig a 4+3 egy jobb megoldás lenne.

A probléma a hátizsák probléma egy alfaja, és dinamikus programozással oldható meg a legkorrektebben, így biztosan minden esetben a minimális bankjegyszámot fogjuk megkapni.

összeg = 12345

bankjegyek[] = {50, 20, 10, 5, 1}

bankjegyek_száma[összeg] = inf //beállítjuk az összes elemét végtelenre, vagy egy nagy számra

bankjegyek_száma[0] = 0

for i = 1-től összeg-ig

. . for_each bankjegy : bankjegyek

. . . . ha bankjegy <= i

. . . . . . ha bankjegyek_száma[i - bankjegy]+1 < bankjegyek_száma[i]

. . . . . . . . bankjegyek_száma[i] := bankjegyek_száma[i - bankjegy]+1

ha bankjegyek_száma[összeg] == inf

. . a megadott bankjegyekből nem lehet kirakni az összeget!

egyébként

. . minimális bankjegyszám := bankjegyek_száma[összeg]

[link]

Ha érdekel, érdemes utánanézni a dinamikus programozás témakörének, ha nem és biztosan nincs 2 olyan pénz i és j hogy i+j>k de k>i és k>j akkor elindulsz a legnagyobbtól és addig vonod ki amíg az összeg > 0, ha az összeg = 0 akkor vége és ha az összeg < 0 akkor veszed a következő pénzt és azzal folytatod inkább.