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

Richiedi il tuo sconto

Track

MIPS Assembly

Esercizi

Zaino

Medio

Introduzione

Lhakpa è una guida alpina e portatrice sherpa. Dopo mesi di attenta pianificazione, la spedizione per cui lavora sta per partire. Verrà pagata in base al valore di ciò che avrà portato fino al campo base.

Davanti a lei ci sono molti oggetti, ognuno con un valore e un peso. Lhakpa prenderebbe volentieri tutti gli oggetti, ma il suo zaino può sostenere solo un peso limitato.

Istruzioni

Il tuo compito è determinare quali oggetti prendere affinché il valore totale della sua selezione sia massimo, tenendo conto della capacità di carico dello zaino.

Gli oggetti saranno rappresentati come una lista di oggetti. Ogni oggetto avrà un peso e un valore. Tutti i valori forniti saranno strettamente positivi. Lhakpa può prendere solo un esemplare di ciascun oggetto.

Per esempio:

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

Knapsack Maximum Weight: 10

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

Registri

Registro	Utilizzo	Tipo	Descrizione
`$a0`	input	indirizzo	array dei pesi degli oggetti
`$a1`	input	indirizzo	array dei valori degli oggetti
`$a2`	input	intero	numero di oggetti
`$a3`	input	intero	peso massimo
`$v0`	output	intero	valore massimo
`$t0-9`	temporaneo	qualsiasi	usato come memoria temporanea