0/1 Knapsack Problem
Hai n oggetti. L’oggetto i pesa weights[i] e vale values[i]. La tua borsa può trasportare un peso totale massimo di capacity. Ogni oggetto è disponibile una sola volta e puoi scegliere se inserirlo interamente nella borsa oppure lasciarlo. Restituisci il valore totale massimo che puoi portare.
Funzione
- weightsinteger-array
- il peso di ciascun elemento
- valuesinteger-array
- il valore di ciascun elemento
- capacityinteger
- il peso massimo che la borsa può trasportare
- Restituisceinteger
- il valore totale più elevato degli elementi i cui pesi rientrano nella capacità
Vincoli
1 ≤ n ≤ 100, doven = weights.length = values.length1 ≤ weights[i] ≤ 10001 ≤ values[i] ≤ 1041 ≤ capacity ≤ 1000
Esempi
- Input
- weights = [4, 2, 3, 5]values = [10, 4, 7, 12]capacity = 7
- Output
- 17
- Spiegazione
- Gli elementi 0 e 2 pesano 4 + 3 = 7 e valgono 10 + 7 = 17. Inserire per primo l’elemento di maggior valore (peso 5, valore 12) lascia spazio solo per l’elemento 1, per un valore di 16.
- Input
- weights = [5, 4, 3]values = [10, 7, 6]capacity = 7
- Output
- 13
- Spiegazione
- Gli oggetti 1 e 2 pesano 4 + 3 = 7 e valgono 7 + 6 = 13. L'oggetto 0 rende 2 per unità di peso, quanto qualsiasi altro oggetto, ma dopo averlo scelto le 2 unità rimaste non bastano per nessun altro oggetto.
- Input
- weights = [6, 8]values = [5, 9]capacity = 5
- Output
- 0
- Spiegazione
- Entrambi gli oggetti pesano più di 5, quindi non entra nulla e la borsa vuota vale 0.
Per approfondire
Supponiamo che la capacità possa arrivare a 10^9, mentre i valori sommati siano al massimo 10^4. In base a cosa indicizzeresti la tabella?
Suggerimenti
Aprili uno alla volta. Ognuno rivela un po’ di più.
Decidi gli elementi in ordine, iniziando dall'elemento 0. Che tu lo metta nello zaino o lo lasci, ti trovi di fronte alla stessa domanda sugli elementi successivi. Quale numero in quella domanda cambia?
Da qui in poi, il valore migliore dipende solo da due numeri: quale elemento stai considerando e quanto spazio rimane. Con 100 elementi e una capacità di 1000, ci sono circa 10^5 coppie di questo tipo, quindi puoi calcolare ciascuna una volta e memorizzarla.
Mantieni
best[c]per ogni capacitàcda 0 acapacity, inizializzando tutti i valori a 0. Per un elemento di pesowe valorev, scorricdacapacitya ritroso fino awe mantieni il valore maggiore trabest[c]ebest[c-w] + v. Procedere a ritroso impedisce che l’elemento venga inserito due volte.
Soluzione
Nessun ordine greedy funziona: mettere per primo l’oggetto di maggior valore fa ottenere 16, non 17, nel primo esempio. Il valore migliore a partire dall’oggetto i dipende solo da i e dallo spazio rimasto, un numero intero fino a 1000. Una cella della tabella per ogni coppia dà O(n × capacity), ed è sufficiente una riga se percorri le capacità in ordine decrescente.
Prova entrambe le opzioni per ogni elemento
Corretto, ma non termina sui test più grandi
Intuizione
Sia best(i, room) il valore massimo degli elementi dall’elemento i in poi che si possono aggiungere con room unità libere; oltre l’ultimo elemento, il valore è 0. Saltare l’elemento i dà best(i+1, room). Includerlo, quando weights[i] ≤ room, dà values[i] + best(i+1, room-weights[i]). Si mantiene il valore maggiore. Ogni combinazione di elementi che entra è una sequenza di scelte tra includere e saltare, e la ricorsione le prova tutte.
Ogni elemento raddoppia i percorsi. Quando tutti e 100 gli elementi entrano insieme, come nel caso di elementi che pesano 10 ciascuno in uno zaino da 1000, si hanno 2^100 percorsi.
Algoritmo
- Scrivi
best(i, room); restituisci 0 quandoisupera l’ultimo elemento. - Imposta
skipsubest(i+1, room). - Se
weights[i] > room, restituisciskip. - Altrimenti restituisci il maggiore tra
skipevalues[i] + best(i+1, room-weights[i]). - Restituisci
best(0, capacity).
def knapsack(weights, values, capacity):
n = len(weights)
# The most value items i, i+1, ... can add with room units of weight left
def best(i, room):
if i == n:
return 0
skip = best(i + 1, room)
if weights[i] > room:
return skip
take = values[i] + best(i + 1, room - weights[i])
return max(skip, take)
return best(0, capacity)Compila una tabella per articolo e capacità
Intuizione
La ricorsione raggiunge la stessa coppia (i, room) lungo molti percorsi. Ci sono al massimo 101 × 1001, circa 10^5, coppie, quindi calcola ciascuna una sola volta.
Sia best[i][c] il valore massimo che i primi i oggetti possono mettere in uno zaino di capacità c; la riga 0 è tutta 0. Per l'oggetto i-1 con peso w e valore v, lasciarlo fuori dà best[i-1][c], mentre inserirlo, quando w ≤ c, dà best[i-1][c-w] + v. La riga i legge solo la riga i-1, quindi ogni oggetto entra in una cella al massimo una volta.
Nel primo esempio, l'oggetto 2 (peso 3, valore 7) porta la capacità 7 a best[2][4] + 7 = 17. L'oggetto 3 offre poi solo best[3][2] + 12 = 16, quindi la risposta resta 17.
Algoritmo
- Crea una tabella di n+1 righe e capacity+1 colonne, tutte a 0.
- Per ogni riga
ida 1 a n, prendiw = weights[i-1]ev = values[i-1]. - Per ogni capacità
c, impostabest[i][c]subest[i-1][c]. - Se
w ≤ cebest[i-1][c-w] + vè maggiore, memorizza invece quel valore. - Restituisci
best[n][capacity].
def knapsack(weights, values, capacity):
n = len(weights)
# best[i][c]: the most value from the first i items within capacity c
best = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
w, v = weights[i - 1], values[i - 1]
for c in range(capacity + 1):
best[i][c] = best[i - 1][c] # leave item i-1 out
if w <= c and best[i - 1][c - w] + v > best[i][c]:
best[i][c] = best[i - 1][c - w] + v # put it in
return best[n][capacity]Una riga, capacità disposte in ordine decrescente
Intuizione
La riga i ha bisogno solo della riga i-1, quindi mantieni una sola riga best[c] e sovrascrivila elemento per elemento. La direzione dello scorrimento determina se la risposta è corretta.
Scorrendo c verso l'alto, best[c-w] potrebbe già includere l'elemento corrente. Un elemento di peso 3 e valore 5 con capacità 6 fa sì che la capacità 3 valga 5; poi la capacità 6 lo legge e diventa 10: due copie. Scorrendo verso il basso da capacity a w, la cella che leggi si trova più in basso di quella che scrivi e verrà sovrascritta in seguito, quindi conserva ancora il valore della riga precedente.
Lo scorrimento verso l'alto è il ciclo corretto quando gli elementi possono essere presi un numero illimitato di volte. Qui il tempo rimane O(n × capacity) e la memoria si riduce a una sola riga.
Algoritmo
- Crea
bestconcapacity + 1elementi, tutti a 0. - Per ogni elemento con peso
we valorev, scorricdacapacityfino aw. - Se
best[c-w] + vsuperabest[c], memorizzalo inbest[c]. - Restituisci
best[capacity].
def knapsack(weights, values, capacity):
# best[c]: the most value from the items seen so far within capacity c
best = [0] * (capacity + 1)
for w, v in zip(weights, values):
# Walk the capacities downward so each item goes in at most once
for c in range(capacity, w - 1, -1):
if best[c - w] + v > best[c]:
best[c] = best[c - w] + v
return best[capacity]
Trappole e casi limite
- Scorrere le capacità in ordine crescente nella versione a una riga fa sì che un elemento venga inserito due volte: un elemento di peso 3 e valore 5 in uno zaino da 6 totalizza 10 invece di 5.
- Una riga di voci
capacityinvece dicapacity + 1. Restituirebest[capacity-1]fa perdere ogni soluzione che riempie esattamente lo zaino, come un peso 1 in uno zaino da 1. - Inizializzare le voci a meno infinito. Lo zaino non deve essere pieno, quindi ogni voce parte da 0; con meno infinito, il terzo esempio restituisce meno infinito invece di 0.
- Un elemento più pesante dello zaino deve essere ignorato. Nel terzo esempio, un intervallo chiuso
w...capacityarresta il programma in Swift, mentre(w+1):(capacity+1)procede all'indietro in R.
Domande frequenti3
Qual è la complessità temporale del problema dello zaino 0/1?
La tabella viene eseguita in tempo O(n × capacity), circa 10^5 passaggi per 100 elementi e una capacità di 1000, e la versione a una riga usa O(capacity) di memoria. Il limite è pseudopolinomiale: cresce con il valore della capacità, non con il numero delle sue cifre. Il problema generale è NP-hard.
Perché un algoritmo greedy non funziona per il problema dello zaino 0/1?
Una regola greedy non annulla mai una scelta, nemmeno quando l'oggetto lascia spazio che nessun altro riempie. Con una capacità di 7, l'oggetto di peso 5 e valore 10 è a pari merito per il miglior rapporto, eppure gli oggetti di peso 4 e 3 insieme valgono 13. L'approccio greedy basato sul rapporto è ottimale solo per il problema dello zaino frazionario, in cui puoi suddividere gli oggetti.
Come fai a trovare quali elementi ha scelto lo zaino 0/1?
Mantieni l’intera tabella e procedi a ritroso da best[n][capacity]. Se best[i][c] è diverso da best[i-1][c], l’elemento i-1 è stato inserito nello zaino, quindi registralo e sottrai il suo peso da c. Altrimenti passa alla riga i-1 mantenendo lo stesso c.
Problemi simili
Problemi che usano le stesse idee. Risolverne due o tre è ciò che fissa uno schema.
def knapsack(weights, values, capacity):
# Scrivi il codice quiTest #1
Test #2
Test #3
Argomenti
weights = [4, 2, 3, 5] values = [10, 4, 7, 12] capacity = 7
Output atteso
17