Ready to put your newfound language skills into use? Get 40% off CodeCrafter's real-world proficiency projects!

تخفیف خود را دریافت کنید

مسیرها

تمرین‌ها

کوله‌پشتی

متوسط

مقدمه

لهکپا یک راهنمای کوهستان و باربر شِرپا است. پس از ماه‌ها برنامه‌ریزی دقیق، اکسپدیشنی که له‌کپا برای آن کار می‌کند، در آستانه‌ی حرکت است. دستمزدی که می‌گیرد، به اندازه‌ی ارزش بارهایی است که تا کمپ اصلی حمل کرده است.

روبه‌روی او وسایل زیادی قرار دارد که هرکدام یک ارزش و یک وزن دارند. له‌کپا با کمال میل همه‌ی آن وسایل را برمی‌دارد، اما کوله‌پشتی‌اش فقط می‌تواند وزن محدودی را در خود جای دهد.

دستورالعمل‌ها

وظیفه‌ی شما این است که تعیین کنید کدام موارد را بردارید تا با در نظر گرفتن ظرفیت حمل کوله‌پشتی، ارزش کل انتخاب‌های او بیشینه شود.

موارد به‌صورت فهرستی از موارد نمایش داده می‌شوند. هر مورد یک وزن و یک ارزش دارد. همه‌ی ارزش‌های داده‌شده اکیداً مثبت هستند. Lhakpa از هر مورد فقط می‌تواند یکی بردارد.

برای مثال:

Items: [
  { "weight": 5, "value": 10 },
  { "weight": 4, "value": 40 },
  { "weight": 6, "value": 30 },
  { "weight": 4, "value": 50 }
]

Knapsack Maximum Weight: 10

در مثال بالا، مورد اول وزن ۵ و ارزش ۱۰ دارد، مورد دوم وزن ۴ و ارزش ۴۰ دارد و به همین ترتیب. در این مثال، Lhakpa برای بیشینه کردن ارزشش باید مورد دوم و چهارم را بردارد؛ این مقدار در این حالت ۹۰ است. او نمی‌تواند بیش از ۹۰ به دست آورد، چون کوله‌پشتی‌اش محدودیت وزن ۱۰ دارد.