Meno problema di modifica con migliaia di denominazioni

Ordina gli oggetti dal valore più alto al più basso. Trova l'oggetto con valore più alto il cui valore è inferiore al numero che stai cercando. Se non esiste un tale oggetto, il metodo fallisce. Se tale oggetto esiste, sottrarre il valore dell'oggetto dal numero di destinazione e utilizzare tale numero di destinazione per chiamare ricorsivamente il metodo di stima delle modifiche. Se quella chiamata ha esito positivo, hai finito. Se fallisce, prova il prossimo oggetto con valore inferiore.

Per lo più devi farlo nel modo più duro nel provare ogni combinazione, ma se si ordina prima l'elenco, c'è un sacco di potature che puoi fare.

Prima di tutto, l'algoritmo avido nella pagina di wikipedia relativa ai problemi di modifica (scegliendo la denominazione più grande non superiore all'importo totale rimanente) è abbastanza efficiente con le giuste strutture dati e spesso, ma non sempre, offre la risposta ottimale. Anche quando la risposta non è ottimale, di solito sarà chiusa, ed è quindi utile come primo passo per la potatura.

Supponiamo che l'algoritmo greedy fornisca una risposta di quattro elementi. Ora devi solo controllare le combinazioni di tre o meno elementi.

L'altra potatura che puoi fare è sui valori degli oggetti. Se il totale è 30, sai di non dover testare alcuna combinazione contenente oggetti del valore di 31 o più. Se la tua prima selezione ha valore 20, sai che la tua seconda selezione deve avere un valore inferiore o uguale a 10. Ancora, questa potatura è abbastanza efficiente su una lista ordinata con le giuste strutture dati.

Questo problema è anche un buon candidato per memoization , dove memorizzi i risultati intermedi invece di ricalcolarli su ogni iterazione.

Inoltre, l'ordine in cui esegui la ricerca fa una grande differenza. Se inizi prima con gli oggetti più grandi, puoi potare molti più percorsi più rapidamente. Non è necessario scorrere prima tutte le combinazioni di $ 1 articoli.

Quindi, a prima vista il problema sembra intrattabile, se sei intelligente riguardo all'ordine in cui entri e fai qualche potatura, dovresti essere in grado di trovare le risposte in un ragionevole lasso di tempo nella pratica. Nel peggiore dei casi, potresti dover interrompere il calcolo dopo un certo periodo di tempo, ma se lo ordini correttamente, avrai una soluzione che è vicina a quella ottimale anche se non hai avuto abbastanza tempo per dimostrare che è sicuramente ottimale. Ai fini di un commercio di giochi, questo potrebbe essere abbastanza buono.

Vorrei rendere questo un commento se non fosse così lungo ... perché non è una risposta definitiva ... ma comunque:

Quindi, immaginando di dover restituire 34 centesimi. Hai 1 quarto, 4 dimes e 3 centesimi. Hai un problema facilmente discernibile che devi dare alla persona 35 centesimi o 33 centesimi, ma non puoi dare il resto esatto.

Per il codice dovrebbe aggiungere un quarto, controlla delta (-9). Salva come delta più vicino.

Niente più trimestri, sposta in penombra. Aggiungi dime, controlla delta (+1). Salva come delta più vicino e fai un salto di dieci centesimi poiché siamo in un delta positivo.

Spostati su nickel, nessuno. Sposta i centesimi e aggiungi i penny mentre delta < 0. Delta finale quando non si usano i penny (-1). Salva come delta più vicino Se il delta negativo è dato come preferenza rispetto al delta positivo poiché l'assoluto è uguale.

Verifica la valuta più bassa, nessuna.

Tuttavia, ci sono altri problemi ... e se fosse necessario fornire all'utente 40 centesimi ...

Devi provare quarter + dime + 3 centesimi con l'algoritmo sopra e il risultato è un delta di -2. Tuttavia, è necessario eseguire il rollback fino ai trimestri e rimuovere una delle valute principali e ricominciare da capo con le valute sottostanti risultanti nella ricerca di 4 dimes delta = 0, DONE.