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

Resgate seu desconto

Trilhas

Haskell

Exercícios

Mochila

Médio

Introdução

Bob é um ladrão. Depois de meses de planejamento cuidadoso, ele finalmente consegue burlar os sistemas de segurança de uma loja de luxo.

Diante dele há vários itens, cada um com um valor e um peso. Bob levaria todos eles de bom grado, mas sua mochila só aguenta um peso limitado. Bob precisa escolher com cuidado quais itens levar para que o valor total da sua seleção seja o maior possível.

Instruções

Sua tarefa é determinar quais itens levar para que o valor total da seleção seja maximizado, 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 informados serão estritamente positivos. Bob 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, Bob deve levar o segundo e o quarto item para maximizar seu valor, que, neste caso, é 90. Ele não consegue mais do que 90, pois sua mochila tem um limite de peso de 10.