Intervista: apportare modifiche per n cents (denominazioni arbitrarie)

Question

Questa domanda si è presentata come parte di un problema sempre più difficile in un'intervista. È iniziata così semplicemente:

(1) Assunzione di una scorta infinita di monete (nelle solite monete da 1, 5, 10, 25 cent). Dato n. centesimi, c'è sempre un modo per apportare modifiche utilizzando le denominazioni normali?

Sì, dal momento che il centesimo divide tutti i possibili valori di n centesimi.

(2) Bene, ora scrivere un programma che accetta n centesimi (positivi), e restituisce un modo possibile di fare il cambiamento per esso

ritorno n centesimi.

(3) Smart ass. Cosa succede se si desidera ridurre al minimo il numero di monete necessarie per apportare la modifica?

Inizia con la più grande denominazione D_I, e prendere il numero massimo di loro in modo tale che non si superi n, m_i. Prendi n - (d_i) (m_i) e ripeti per la prossima denominazione più grande.

(4) Bene, puoi dimostrare che questa soluzione è ottimale?

Sì, {blah, blah}

(5) Ok, * sorriso *, ora cosa succede se, oltre ai n centesimi, è stata data una matrice arbitraria di dimensioni che consiste di denominazioni arbitrarie? È possibile assumere ogni denominazione si verifica solo una volta nella matrice, e che tutte le denominazioni sono positivi

Il mio primo pensiero era solo per ordinare l'array delle denominazioni, e applicare la stessa logica a (4). Fortunatamente, prima di comunicarlo, mi sono accorto e ho capito che non avrebbe funzionato. Ma ora mi sono reso conto che ero in un sottaceto.

Il mio prossimo pensiero è stato quello di applicare il problema della somma parziale a ogni divisore di n, ma ho capito che probabilmente era eccessivo. La soluzione che ho finito per fornire ha appena usato il Change-making problem e l'ho cortocircuitato quando ho trovato la soluzione nella soluzione. Mi sento come se ci deve essere un modo più intelligente di fare questo però ..

Il problema si riduce a: Dato un insieme finito S dei numeri naturali distinti, trovare una combinazione lineare di elementi di S che (1) somma ad un altro numero naturale n, (2) minimizzare la somma dei coefficienti nella lin.combinazione

Answer 1

realtà questo problema è stato studiato come sistemi a moneta canoniche, e abbiamo anche ottenuto una carta circa come determinare se un dato sistema di monete può supportare una soluzione avida. Il documento originale può darti alcuni spunti: Canonical coin systems for change-making problems.

In alternativa, è possibile utilizzare Google la parola chiave "Sistemi di monete canoniche" per ulteriori informazioni.

Answer 2

Sia d[pos][sum] tramite il numero minimo di monete necessarie per effettuare un cambio di sum denaro utilizzando solo i primi pos denonimations o infinito se è impossibile

Let a[i] essere denonimation di moneta i

Può essere inteso in modo ricorsivo Le regole 1) e 2) saranno basate sulla ricorsione.

1) d[any pos][0]=0 (possiamo restituire i soldi a nessuna moneta)

2) d[1][each sum] = se (a [1]! = Somma) Infinity altro 1 (Siamo in grado di fare un cambiamento di somma per una moneta unica se ha denonimation sum)

3) Else:

Possiamo scegliere punto corrente per fare un cambiamento o no sceglierlo

d[pos][sum]=min(choose,d[pos-1][sum]) dove

choose=d[pos-1][sum-a[i]] se sum> = a [i], Infinity altrimenti

Se non scegliamo il numero di monete pos, cerchiamo di fare la stessa modifica con pos-1 monete. Quindi, d[pos-1][sum]

Se si sceglie il numero di moneta pos, quindi dobbiamo solo fare un cambiamento per somma che è minore di corrente per denonimazione di pos. d[pos-1][sum-a[i]]

Ma possiamo scegliere il numero di monete pos solo se è denonimation è minore o uguale alla somma corrente

---

In soluzione reale

a) ricorsione deve essere sostituito da ciclo

oppure

b) Dobbiamo memorizzare was[pos][sum] - se il valore d[pos][sum] è stato conteggiato.

quando proviamo a contare d[pos][sum]

se was[pos][sum]==true semplicemente restituirlo. (Il valore viene già conteggiato)

altro: contare in base ai passi 1-3 e impostare was[pos][sum] true

Answer 3

C'è una risposta facile che fornisce tempo e spazio pseudo-polinomiali in termini di n (vale a diretempo di esecuzione e utilizzo della memoria proporzionale a n invece della dimensione di input che è log n), e una risposta più difficile ma più utile che può portare a un vero tempo polinomiale per tagli fissi.

Creare un array A di dimensione n. Questo array memorizza il numero minimo di monete necessarie per fare k cents per ogni k = 1 a n, dove A [k] = -1 se è impossibile fare k cent. Puoi riempire questo array in sequenza da k = 1 a n, registrando A [k] = 1 se k è una delle tue denominazioni, e altrimenti registrando A [k] = M + 1 dove M è il minimo di A [k - C] su tutte le denominazioni C (e A [k] = -1 se tutti i k-C sono positivi o A [k - C] = -1). Quindi, una volta raggiunto n, puoi tornare indietro attraverso l'array iniziando da n e sottraendo ogni denominazione per vedere quale denominazione ti ha dato la risposta ottimale, risalendo attraverso tutte le monete usate per formare la soluzione ottimale.

Questa è la risposta facile. Ora, la risposta difficile per n molto grande rispetto alle denominazioni è capire quando puoi prendere una scorciatoia e prendere la moneta con la moneta più grande per un po 'finché il totale dei centesimi rimanenti scende sotto un certo valore. Non so come risolvere quel valore, ma è possibile, e il valore esiste sempre, e una volta che lo hai capito, non importa quanto sia grande, tutto quello che devi fare è calcolare quanti la moneta più grande da usare per prima (O (log n)), e poi risolvere una volta che sei sotto il valore (tempo costante se consideri le denominazioni fisse, o tempo di esecuzione che dipende dalle denominazioni (ma non n) se le denominazioni non sono riparati).