کوله‌پشتی

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

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

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

برای مثال:

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

Knapsack Maximum Weight: 10

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

---

منبع

Wikipedia