Problema dello zaino
Lezione 7 di 15 del corso Programmazione dinamica 101 di Coddy.
Il problema dello zaino è un classico problema di ottimizzazione nell'informatica. L'enunciato del problema è semplice: dato un insieme di oggetti, ciascuno con un peso e un valore, determina quali oggetti includere in una raccolta affinché il peso totale sia minore o uguale a un limite dato e il valore totale sia massimizzato.
Esistono due tipi di problema dello zaino:
- Problema dello zaino 0/1: in questa versione, il ladro non può prendere frazioni dell'oggetto: o lo prende interamente oppure lo lascia.
- Problema dello zaino frazionario: in questa versione, il ladro può prendere frazioni dell'oggetto, cioè può prenderne una parte.
Sfida
MedioScrivi una funzione chiamata knapsack che risolva il problema dello zaino 0/1. La funzione deve accettare tre input:
- Un elenco dei pesi di n elementi (w1, w2, ... , wn).
- Un elenco dei valori di n elementi (v1, v2, ... , vn).
- La capacità massima di peso dello zaino (W).
La funzione deve quindi restituire il valore massimo ottenibile riempiendo lo zaino.
Ad esempio:
weights = [10, 20, 30]
values = [60, 100, 120]
W = 50
knapsack(weights, values, W)Output:
220 # taking the 2 largest itemsProvalo tu
def knapsack(wrights, values, W):
# Scrivi il codice quiTutte le lezioni di Programmazione dinamica 101
1Introduzione alla DP
Che cos’è la programmazione dinamica?Perché è importante?Applicazioni in vari campi3Algoritmi di programmazione dinamica
Sottosequenza comune più lungaProblema dello zainoProblema del cambio delle moneteDistanza di modificaEsercitati da solo: Compilatore Python online