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

Aproveita o teu desconto

Percursos

MIPS Assembly

Exercícios

Mochila

Médio

Introdução

A Lhakpa é uma xerpa, guia de montanha e carregadora. Depois de meses de planeamento cuidadoso, a expedição para a qual a Lhakpa trabalha está prestes a partir. Vai ser paga pelo valor daquilo que transportar até ao acampamento base.

À frente dela estão muitos itens, cada um com um valor e um peso. A Lhakpa levaria todos os itens de bom grado, mas a mochila dela só aguenta um certo peso.

Instruções

A tua tarefa é determinar que itens levar, de modo a maximizar o valor total da sua escolha, tendo em conta a capacidade de carga da mochila.

Os itens serão representados como uma lista de itens. Cada item terá um peso e um valor. Todos os valores dados serão estritamente positivos. A Lhakpa só pode levar um de cada item.

Por exemplo:

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

Knapsack Maximum Weight: 10

No exemplo acima, o primeiro item tem peso 5 e valor 10, o segundo item tem peso 4 e valor 40, e assim por diante. Neste exemplo, a Lhakpa deve levar o segundo e o quarto item para maximizar o seu valor, que, neste caso, é 90. Não pode obter mais do que 90, uma vez que a sua mochila tem um limite de peso de 10.

Registos

Registo	Utilização	Tipo	Descrição
`$a0`	entrada	endereço	array com os pesos dos itens
`$a1`	entrada	endereço	array com os valores dos itens
`$a2`	entrada	inteiro	número de itens
`$a3`	entrada	inteiro	peso máximo
`$v0`	saída	inteiro	valor máximo
`$t0-9`	temporário	qualquer	usado para armazenamento temporário