नैपसैक

निर्देश

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

सभी आइटम एक ऐरे के रूप में दर्शाए जाएँगे। हर आइटम का एक वज़न और एक वैल्यू होगी। दी गई सभी वैल्यू पूर्णतः धनात्मक होंगी। बॉब हर आइटम में से सिर्फ एक ही ले सकता है।

उदाहरण के लिए:

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 है, और इसी तरह बाकी आइटमों का भी। इस उदाहरण में बॉब को अपनी वैल्यू अधिकतम करने के लिए दूसरा और चौथा आइटम लेना चाहिए। यहाँ उसकी वैल्यू 90 बनती है। वह 90 से ज़्यादा वैल्यू नहीं पा सकता, क्योंकि उसके नैपसैक की वज़न सीमा 10 है।

---

स्रोत

Wikipedia