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.
Notas específicas do WebAssembly
Os itens são passados através da memória linear, com o primeiro item no deslocamento 0.
Cada item é representado por um par de inteiros de 32 bits.
O primeiro número do par é o peso e o segundo é o valor.
Por exemplo, considera uma lista de dois itens, em que o primeiro tem weight=1, value=2 e o segundo weight=5, value=8.
Assim, a lista ficaria deste modo na memória:
| 00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 | 13 | 14 | 15 |
| - item 1 weight - | -- item 1 value - | - item 2 weight - | -- item 2 value - |
|0x01,0x00,0x00,0x00|0x02,0x00,0x00,0x00|0x05,0x00,0x00,0x00|0x08,0x00,0x00,0x00|
Se quiseres, podes sobrescrever os endereços da memória linear usados para os dados de entrada.
