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.
Notas específicas do WebAssembly
Os itens são passados pela memória linear, com o primeiro item no offset 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, considere uma lista de dois itens, em que o primeiro tem weight=1, value=2 e o segundo weight=5, value=8.
Então, a lista ficaria assim 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 preferir, você pode sobrescrever os endereços da memória linear usados para a entrada.
