नैपसैक

निर्देश

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

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

ट्रैक से जुड़ी खास बातें

Scheme वाले संस्करण में आर्गुमेंट ये होते हैं: नैपसैक की capacity, weights का एक ऐरे, और values का एक ऐरे। इनपुट की जाँच करने की ज़रूरत नहीं होगी। टेस्ट के इनपुट में सही वैल्यू होती हैं और ऐरे की लंबाई भी समान होती है।

---

स्रोत

Wikipedia