नैपसैक

निर्देश

आपको यह तय करना है कि कौन-सी चीज़ें उठानी हैं, जिससे उसके चुनाव की कुल वैल्यू अधिकतम हो जाए। साथ ही यह भी ध्यान रखना है कि नैपसैक में कितना वज़न रखा जा सकता है।

चीज़ें एक ऐरे के रूप में दी जाएँगी। हर चीज़ का एक वज़न और एक वैल्यू होगा। दी गई सभी वैल्यू पूरी तरह धनात्मक होंगी। 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 है।

---

स्रोत

Wikipedia