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

Aproveita o teu desconto

Percursos

Haskell

Exercícios

Mochila

Médio

Introdução

O Bob é um ladrão. Depois de meses de planeamento cuidadoso, consegue finalmente quebrar os sistemas de segurança de uma loja de luxo.

À sua frente estão muitos artigos, cada um com um valor e um peso. O Bob levaria todos os artigos de bom grado, mas a mochila só aguenta um certo peso. O Bob tem de ponderar cuidadosamente que artigos levar, para que o valor total da sua seleção seja o máximo possível.

Instruções

A tua tarefa é determinar que itens o Bob deve levar, de modo a maximizar o valor total da seleção, tendo em conta a capacidade de carga da mochila.

Os itens serão representados como uma lista de itens. Cada item tem um peso e um valor. Todos os valores dados são estritamente positivos. O Bob 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, o Bob deve levar o segundo e o quarto item para maximizar o seu valor, que, neste caso, é 90. Não consegue obter mais do que 90, porque a mochila tem um limite de peso de 10.