Un algoritmo di imballaggio & # 8230; tipo

Question

Data una serie di articoli, ognuno dei quali ha un valore e cost , qual è l'algoritmo migliore per determinare gli elementi richiesti per raggiungere un valore minimo al costo minimo? ad esempio:

Item: Value -> Cost
-------------------
A     20   -> 11
B     7    -> 5
C     1    -> 2

MinValue = 30
naive solution: A + B + C + C + C. Value: 30, Cost 22
best option: A + B + B.            Value: 34, Cost 21

Nota che il valore complessivo: il rapporto di costo alla fine è irrilevante ( A + A ti darebbe il miglior rapporto qualità-prezzo, ma A + B + B è un'opzione più economica che raggiunge il valore minimo).

Answer 1

Questo è il problema dello zaino. (Cioè, la versione di decisione di questo problema è la stessa della versione di decisione del problema dello zaino, sebbene la versione di ottimizzazione del problema dello zaino sia di solito dichiarata diversamente.) È NP-difficile (il che significa che nessun algoritmo è noto che è polinomio nella "dimensione" - numero di bit - nell'input). Ma se i tuoi numeri sono piccoli (il più grande "valore" nell'input, diciamo; i costi non contano), allora c'è una semplice soluzione di programmazione dinamica.

Lascia che best [v] sia il costo minimo per ottenere un valore di (esattamente) v. Quindi puoi calcolare i valori best [] per tutti v, inizializzando tutti i migliori [v] su infinito e):

best[0] = 0
best[v] = min_(items i){cost[i] + best[v-value[i]]}

Quindi guarda al meglio [v] per i valori fino al minimo desiderato più il valore più grande; il più piccolo di questi ti darà il costo.

Se vuoi gli articoli reali (e non solo il costo minimo), puoi conservare alcuni dati extra, o semplicemente guardare attraverso l'array dei migliori [] se ne dedurre.

Answer 2

Questo problema è noto come programmazione lineare intera. È NP-difficile. Tuttavia, per piccoli problemi come il tuo esempio, è banale creare poche righe di codice per forzare semplicemente tutte le basse combinazioni di scelte di acquisto.

NP-harddoes non significa impossibile o addirittura costoso, significa che il tuo problema diventa rapidamente più lento da risolvere con problemi su larga scala. Nel tuo caso con solo tre elementi, puoi risolverlo in soli microsecondi.

Per la domanda esatta su quale sia l'algoritmo migliore in generale .. ci sono interi libri di testo su di esso. Un buon inizio è buona vecchia Wikipedia.

Answer 3

Modifica Questa risposta è stata redatta a causa di errori di fatto. Seguire i consigli in questo ti farà solo male.

Questo non è in realtà il problema degli zaini, poiché si presume che non sia possibile imballare più articoli di quanti siano gli spazi in alcuni contenitori. Nel tuo caso, vuoi trovare la combinazione più economica che riempie lo spazio, tenendo conto del fatto che potrebbe verificarsi un overflow.

La mia soluzione, che non conosco sia ottimale ma dovrebbe essere abbastanza vicina, sarebbe quella di calcolare per ogni articolo il rapporto costi / benefici, trovare l'articolo con il più alto vantaggio in termini di costi e riempire la struttura con questo articolo fino a non c'è spazio per un altro oggetto. Quindi testerei per vedere se c'era una combinazione con uno qualsiasi degli altri articoli disponibili che potesse riempire lo slot disponibile per meno del costo di uno degli articoli più economici e quindi se esiste una tale soluzione, usa quella combinazione altrimenti usa un altro degli articoli più economici.

Amenddum Questo potrebbe anche essere NP-completo, ma non ne sono ancora sicuro. Comunque per tutti gli scopi pratici questa variazione dovrebbe essere molto più veloce della soluzione ingenua.