Вступ
Лхакпа - шерпа, гірський гід і носій.
Після місяців ретельного планування експедиція, у якій працює Лхакпа, ось-ось вирушить.
Їй заплатять вартість того, що вона донесла до базового табору.
Перед нею лежать численні предмети, кожен зі своєю цінністю та вагою.
Лхакпа охоче взяла б усі ці предмети, але її рюкзак може вмістити лише обмежену вагу.
Вказівки
Визначте, які предмети взяти, щоб загальна цінність її вибору була максимальною, зважаючи на вантажопідйомність рюкзака.
Предмети буде представлено як масив предметів.
Кожен предмет матиме вагу та цінність.
Усі наведені значення будуть строго додатними.
Lhakpa може взяти лише по одному предмету кожного виду.
Наприклад:
Items: [
{ "weight": 5, "value": 10 },
{ "weight": 4, "value": 40 },
{ "weight": 6, "value": 30 },
{ "weight": 4, "value": 50 }
]
Knapsack Maximum Weight: 10
У наведеному прикладі перший предмет має вагу 5 і цінність 10, другий предмет має вагу 4 і цінність 40, і так далі.
У цьому прикладі Lhakpa має взяти другий і четвертий предмети, щоб максимізувати свою цінність, яка в цьому випадку дорівнює 90.
Вона не може отримати більше ніж 90, оскільки її рюкзак має обмеження ваги 10.
Нотатки щодо WebAssembly
Елементи передаються через лінійну памʼять, причому перший елемент розташований зі зсувом 0.
Кожен елемент представлено парою 32-бітних цілих чисел.
Перше число в парі - вага, а друге - значення.
Наприклад, розглянемо список із двох елементів, де перший має weight=1, value=2, а другий - weight=5, value=8.
Отже, у памʼяті цей список матиме такий вигляд:
| 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|
За бажанням можна перезаписати адреси лінійної памʼяті, що використовуються для вхідних даних.
