Ready to put your newfound language skills into use? Get 40% off CodeCrafter's real-world proficiency projects!

Richiedi il tuo sconto

Track

Haskell

Esercizi

Zaino

Medio

Introduzione

Bob è un ladro. Dopo mesi di attenta pianificazione, riesce finalmente a violare i sistemi di sicurezza di un negozio di lusso.

Davanti a lui ci sono molti oggetti, ognuno con un valore e un peso. Bob prenderebbe volentieri tutti gli oggetti, ma il suo zaino può contenerne solo fino a un certo peso. Bob deve valutare con attenzione quali oggetti prendere, così che il valore totale della sua selezione sia massimo.

Istruzioni

Il tuo compito è determinare quali elementi prendere, in modo che il valore totale della selezione di Bob sia il massimo possibile, tenendo conto della capacità di carico dello zaino.

Gli elementi saranno rappresentati come un array di elementi. Ogni elemento avrà un weight e un value. Tutti i valori forniti saranno strettamente positivi. Bob può prendere un solo esemplare di ogni elemento.

Ad esempio:

Items: [
  { "weight": 5, "value": 10 },
  { "weight": 4, "value": 40 },
  { "weight": 6, "value": 30 },
  { "weight": 4, "value": 50 }
]

Knapsack Maximum Weight: 10

Nell'esempio qui sopra, il primo elemento ha weight 5 e value 10, il secondo elemento ha weight 4 e value 40, e così via. In questo caso, Bob dovrebbe prendere il secondo e il quarto elemento per massimizzare il suo valore, che è 90. Non può ottenere più di 90, dato che il suo zaino ha un limite di peso di 10.