Knapsack 0/1: prendere o lasciare
Massimizzare il valore entro un limite di peso
Knapsack 0/1: prendere o lasciare è una lezione Competitive Programming Academy gratuita su CoddyKit. Questa è la lezione 1 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Competitive Programming Academy, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Competitive Programming Academy include 4 lezioni in totale.
Il problema dello zaino
Ha una borsa con un limite di peso e una pila di oggetti. Il problema dello zaino 0/1 chiede: quali oggetti massimizzano il valore senza superare la capacità? 🎒
Prendere o lasciare
La dicitura 0/1 significa che ogni oggetto viene preso interamente oppure ignorato del tutto. Non è mai possibile prenderne metà, quindi ogni scelta è sì o no.
Perché la strategia greedy fallisce
Prendere per primo l'oggetto più economico o quello di maggior valore può sprecare capacità. La scorciatoia greedy qui non funziona, quindi è necessario considerare le combinazioni effettive.
I due input
Vengono fornite due liste parallele: un peso e un valore per ogni oggetto, oltre a una capacità. L'oggetto i ha peso wt[i] e valore val[i].
wt = [1, 3, 4, 5]
val = [1, 4, 5, 7]
cap = 7Definire lo stato
Definisca dp[i][w] come il valore migliore ottenibile usando i primi i oggetti con capacità w. Dare un nome preciso allo stato è l'aspetto fondamentale.
La scelta di ignorare
Se ignora l'oggetto i, il valore è quello già ottenuto: dp[i-1][w]. La capacità rimane intatta per il resto.
La scelta di prendere
Se prende l'oggetto i, aggiunge il suo valore e riduce la capacità: val[i] + dp[i-1][w - wt[i]]. Questo è possibile solo quando w è almeno wt[i].
Scegliere il ramo migliore
La ricorrenza conserva semplicemente l'opzione maggiore usando max. Ogni cella si affida alle risposte già calcolate nella riga precedente.
dp[i][w] = max(dp[i-1][w],
val[i] + dp[i-1][w - wt[i]])La riga base
Con zero oggetti è possibile trasportare valore zero a qualsiasi capacità. Questo caso base riempie la prima riga con tutti zeri, fornendo il punto di partenza.
dp = [[0] * (cap + 1) for _ in range(n + 1)]Riempire la tabella
Scorra gli oggetti nel ciclo esterno e le capacità in quello interno. Ogni cella legge solo la riga precedente, quindi un'unica scansione riempie tutto.
for i in range(1, n + 1):
for w in range(cap + 1):
dp[i][w] = dp[i-1][w]Leggere la risposta
La cella in basso a destra, dp[n][cap], contiene il valore massimo per tutti gli oggetti e l'intera capacità. Questa singola cella è la risposta finale.
Verifica rapida
Verifichi la ricorrenza fondamentale dello zaino 0/1.
Riepilogo
Ha imparato il problema dello zaino 0/1: ogni oggetto si prende o si lascia, dp[i][w] conserva il migliore tra ignorarlo e prenderlo, e dp[n][cap] è la risposta. 🎉
Impara Python con un tutor IA — gratis
Scrivi ed esegui vero codice nel tuo browser, ricevi aiuto istantaneo da un tutor IA disponibile 24/7, e riprendi da dove hai lasciato sul web o nell'app.
- Corsi
- 30
- Lezioni
- 120
Domande Frequenti
La lezione «Knapsack 0/1: prendere o lasciare» è gratuita?
Sì — il testo completo di «Knapsack 0/1: prendere o lasciare» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Competitive Programming Academy, passa a CoddyKit PRO. Il corso Competitive Programming Academy include 4 lezioni in totale.
Cosa imparerò in «Knapsack 0/1: prendere o lasciare»?
Massimizzare il valore entro un limite di peso Eserciti Competitive Programming Academy con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare Competitive Programming Academy?
Non è richiesta alcuna esperienza precedente. Competitive Programming Academy su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 1 di 4.
Quanto tempo richiede la lezione «Knapsack 0/1: prendere o lasciare»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione Competitive Programming Academy?
Sì. Ogni lezione Competitive Programming Academy include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- Knapsack 0/1: prendere o lasciare
- Knapsack ottimizzato nello spazio
- DP illimitato e cambio di monete
- Somma di sottoinsiemi e partizionamento