مقدمه
لهکپا یک راهنمای کوهستان و باربر شِرپا است.
پس از ماهها برنامهریزی دقیق، اکسپدیشنی که لهکپا برای آن کار میکند، در آستانهی حرکت است.
دستمزدی که میگیرد، به اندازهی ارزش بارهایی است که تا کمپ اصلی حمل کرده است.
روبهروی او وسایل زیادی قرار دارد که هرکدام یک ارزش و یک وزن دارند.
لهکپا با کمال میل همهی آن وسایل را برمیدارد، اما کولهپشتیاش فقط میتواند وزن محدودی را در خود جای دهد.
دستورالعملها
وظیفهی شما این است که تعیین کنید کدام موارد را بردارید تا با در نظر گرفتن ظرفیت حمل کولهپشتی، ارزش کل انتخابهای او بیشینه شود.
موارد بهصورت فهرستی از موارد نمایش داده میشوند.
هر مورد یک وزن و یک ارزش دارد.
همهی ارزشهای دادهشده اکیداً مثبت هستند.
Lhakpa از هر مورد فقط میتواند یکی بردارد.
برای مثال:
Items: [
{ "weight": 5, "value": 10 },
{ "weight": 4, "value": 40 },
{ "weight": 6, "value": 30 },
{ "weight": 4, "value": 50 }
]
Knapsack Maximum Weight: 10
در مثال بالا، مورد اول وزن ۵ و ارزش ۱۰ دارد، مورد دوم وزن ۴ و ارزش ۴۰ دارد و به همین ترتیب.
در این مثال، Lhakpa برای بیشینه کردن ارزشش باید مورد دوم و چهارم را بردارد؛ این مقدار در این حالت ۹۰ است.
او نمیتواند بیش از ۹۰ به دست آورد، چون کولهپشتیاش محدودیت وزن ۱۰ دارد.
نکات مخصوص WebAssembly
عنصرها از طریق حافظهی خطی منتقل میشوند و عنصر اول در آفست ۰ قرار دارد.
هر عنصر بهصورت یک جفت عدد صحیح ۳۲ بیتی نمایش داده میشود.
عدد اول در هر جفت وزن است و عدد دوم مقدار.
برای مثال، فهرستی از دو عنصر را در نظر بگیرید که اولی 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|
اگر بخواهید، میتوانید آدرسهای حافظهی خطی را که برای ورودی به کار میرود بازنویسی کنید.
