Introducción
Lhakpa es guía de montaña y porteadora Sherpa.
Tras meses de una planificación minuciosa, la expedición para la que trabaja Lhakpa está a punto de partir.
Se le pagará el valor de lo que llevó hasta el campo base.
Frente a ella hay muchos objetos, cada uno con un valor y un peso.
Lhakpa no dudaría en llevárselos todos, pero su mochila solo puede cargar cierto peso.
Instrucciones
Tu tarea consiste en determinar qué objetos tomar para que el valor total de su selección sea el máximo posible, teniendo en cuenta la capacidad de carga de la mochila.
Los objetos se representarán como un array de objetos.
Cada objeto tendrá un peso y un valor.
Todos los valores dados serán estrictamente positivos.
Lhakpa solo puede tomar uno de cada objeto.
Por ejemplo:
Items: [
{ "weight": 5, "value": 10 },
{ "weight": 4, "value": 40 },
{ "weight": 6, "value": 30 },
{ "weight": 4, "value": 50 }
]
Knapsack Maximum Weight: 10
En el ejemplo anterior, el primer objeto tiene un peso de 5 y un valor de 10, el segundo objeto tiene un peso de 4 y un valor de 40, y así sucesivamente.
En este ejemplo, Lhakpa debería tomar el segundo y el cuarto objeto para maximizar su valor, que, en este caso, es 90.
No puede conseguir más de 90, ya que su mochila tiene un límite de peso de 10.
Notas específicas de WebAssembly
Los elementos se pasan a través de la memoria lineal, con el primer elemento en el desplazamiento 0.
Cada elemento se representa como un par de números enteros de 32 bits.
El primer número del par es el peso y el segundo es el valor.
Por ejemplo, considera un array de dos elementos, donde el primero tiene weight=1, value=2 y el segundo weight=5, value=8.
El array se vería así en memoria:
| 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|
Si lo prefieres, puedes sobrescribir las direcciones de la memoria lineal usadas para la entrada.
