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

Resgate seu desconto

Trilhas

Kotlin

Exercícios

Mochila

Médio

Introdução

Lhakpa é uma sherpa, guia e carregadora de montanha. Depois de meses de planejamento cuidadoso, a expedição para a qual Lhakpa trabalha está prestes a partir. Ela receberá o valor que carregou até o acampamento base.

Diante dela há muitos itens, cada um com um valor e um peso. Lhakpa levaria todos os itens de bom grado, mas sua mochila suporta apenas um determinado peso.

Instruções

Sua tarefa é determinar quais itens levar para que o valor total da seleção dela seja o maior possível, levando 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 fornecidos serão estritamente positivos. Lhakpa pode levar apenas 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, Lhakpa deve levar o segundo e o quarto item para maximizar seu valor, que, neste caso, é 90. Ela não consegue mais do que 90, pois sua mochila tem um limite de peso de 10.