[teoria] Calcolo banconote per fare un certo totale

[kevinpirola]

Ciao a tutti,

mi sto scervellando su un problema di natura combinatorio-matematica presumo.

In poche parole, dati dei valori standard (ipotizziamo delle banconote) devo poter calcolare, dato un totale, quali sono le combinazioni di valori che posso usare per raggiungerlo più o meno precisamente. esempio

posso usare banconote da 100, 200 e 500 (che di sti tempi vedo poco )

devo raggiungere il totale di 1000, posso farlo con:
10 da 100
5 da 200
2 da 500
1 da 500, 2 da 200, 1 da 100
1 da 500, 1 da 200, 3 da 100
1 da 500, 5 da 100
2 da 200, 6 da 100
1 da 200, 8 da 100

oppure posso fare "circa"
2 da 500 e 1 da 100
1 da 500 e 2 da 200
1 da 500 e 3 da 200

ecc ecc

sarò io a dargli un range di combinazioni e magari dargli come parametro se voglio il massimo numero di banconote o il minimo ecc ecc

sapete dirmi su cosa si basa questa teoria? che cosa mi devo studiare?

[WarDuck]

Proviamo a scomporre il problema.

Se il problema fosse esclusivamente del tipo "scegliere la combinazione con meno monete", io userei una strategia "greedy", scegliendo sempre la moneta più grande possibile tra tutte, controllando ovviamente se questa moneta superi o meno il rimanente.

Se supera il rimanente, allora passo ad una moneta più piccola, altrimenti sottraggo il valore dal rimanente e così via fino ad arrivare al risultato.

Questo sempre che il numero di monete a disposizione sia illimitato (ma non dovrebbe essere difficile estenderlo al caso limitato).

Credo inoltre si possa estendere questo algoritmo per generare tutte le combinazioni possibili.

In particolare potresti far finta di non avere alcune tagli di moneta e far girare nuovamente l'algoritmo.

Ad esempio:

voglio calcolare 1000 e ho banconote { 500, 200, 100 }

Quindi il programma tira fuori la soluzione {500 + 500}

A questo punto supponi di avere solo banconote {200, 100}

Il programma tirerà fuori una nuova soluzione, { 5*200 }

Supponi di avere solo {100}:

Il programma tirerà fuori 10*100.

Dunque potresti applicare la mia soluzione più volte, facendo finta di non avere di volta in volta il taglio più grande.

A spanne per una singola soluzione dovresti fare qualcosa del genere:

var totale;

var rimanente = totale;

var moneta_corrente = { moneta più grande };

while rimanente > 0:
   while moneta_corrente > rimanente:
      moneta_corrente = {moneta più piccola della precedente}

   rimanente = rimanente - moneta_corrente

Due cose:

1) non l'ho ricontrollato, quindi potrebbero esserci scritte castronerie.
2) dovresti valutare il caso in cui non riesci con i tagli che hai a dare precisamente il risultato.

[kevinpirola]

mm mi piace come idea, posso praticamente mettere i valori in una lista e passo dopo passo escludere uno o l'altro valore, questo pomeriggio provo a buttare giù qualcosa, intanto mi guardo il "greedy" che mi hai detto

però mi resta il dubbio, io avevo già sentito parlare di un algoritmo del genere solo che non ricordo....

[gugoXX]

Problema simile gia' studiato qui, prova a dare un'occhiata
(Il tuo e' di fatto il sottoproblema 3 di quello qui sotto)

http://www.hwupgrade.it/forum/showthread.php?t=1884158

[marco.r]

E' una variante del classico problema del knapsack (o problema dello zaino).
Se ricordo bene nel caso di minimizzazione puoi considerarlo come un problema di knapsack con peso proporzionale al valore delle banconote e valore unitario per qualsiasi banconota. Nel caso di massimizzazione puoi considerare il problema inverso.
Ogni buon testo di algoritmi copre l'argomento; in alternativa prova a vedere qualche riferimento di wikipedia: http://en.wikipedia.org/wiki/Knapsack_problem

[banryu79]

@kevinpirola: ma vuoi tutte le combinazioni possibili per raggiungere la cifra data o solo quelle che minimizzano/massimizzano le banconote usate?

Prendendo come riferimento l'esempio di WarDuck:

Ad esempio:

voglio calcolare 1000 e ho banconote { 500, 200, 100 }

Quindi il programma tira fuori la soluzione {500 + 500}

A questo punto supponi di avere solo banconote {200, 100}

Il programma tirerà fuori una nuova soluzione, { 5*200 }

Supponi di avere solo {100}:

Il programma tirerà fuori 10*100.

Dunque potresti applicare la mia soluzione più volte, facendo finta di non avere di volta in volta il taglio più grande.

Qui per fare 1000 c'è anche la combinazione {500 + 2*200 + 100}, ma non salta fuori, infatti lui parlava di minimizzare le banconote usate.
Tu hai questo requisito (minimizzazione) oppure no (devi calcolare tutte le combinazioni possibili)?

[Filly95]

E se uno volesse calcolare il mumero massimo di soluzioni che questo problema genera come si può fare?

[Mettiu_]

Originariamente inviato da Filly95

E se uno volesse calcolare il mumero massimo di soluzioni che questo problema genera come si può fare?

Non vorrei dire una stupidaggine ma mi sembra che sia un problema NP-hard quindi non si può definire una formula (o un algoritmo) che ti faccio quel calcolo in tempo costante O(n). Se questo fosse vero, vuol dire che l'unico modo possibile per fare il calcolo è 'provarle tutte' e contarle (algoritmo non polinomiale).
Ecco, ora di sicuro qualcuno tira fuori una formula che con due moltiplicazioni risolve tutto