0/1 Knapsack Problem using Dynamic Programming in Hindi | 0/1 नैपसैक समस्या डायनेमिक प्रोग्रामिंग द्वारा

0/1 नैपसैक समस्या क्या है? (0/1 Knapsack Problem in Hindi)

0/1 नैपसैक समस्या (0/1 Knapsack Problem) एक ऑप्टिमाइज़ेशन समस्या है जिसमें एक निश्चित क्षमता (Capacity) वाले बैग में वस्तुओं (Items) को इस प्रकार से रखा जाता है कि कुल मूल्य (Total Value) अधिकतम हो।

0/1 नैपसैक समस्या की विशेषताएँ (Characteristics of 0/1 Knapsack Problem)

• प्रत्येक वस्तु को या तो पूरी तरह से बैग में रखा जा सकता है या बिल्कुल नहीं।
• वस्तु को टुकड़ों में विभाजित नहीं किया जा सकता।
• समस्या को डायनेमिक प्रोग्रामिंग (Dynamic Programming) का उपयोग करके हल किया जाता है।

0/1 नैपसैक समस्या का गणितीय स्वरूप (Mathematical Formulation of 0/1 Knapsack)

मान लीजिए कि हमारे पास n वस्तुएं हैं और प्रत्येक वस्तु का एक निश्चित भार (Weight) और मूल्य (Value) है।

• W: बैग की अधिकतम क्षमता
• wt[i]: वस्तु i का भार
• val[i]: वस्तु i का मूल्य

उद्देश्य (Objective Function):

Maximize:  Σ val[i]  (जहाँ i उन वस्तुओं का सूचकांक है जो बैग में हैं)
Subject to: Σ wt[i] ≤ W

डायनेमिक प्रोग्रामिंग द्वारा 0/1 नैपसैक समस्या का हल (Solving 0/1 Knapsack using Dynamic Programming)

समस्या को हल करने के लिए एक 2D डायनेमिक प्रोग्रामिंग टेबल बनाई जाती है।

Knapsack(W, wt[], val[], n)
1. एक टेबल dp[][] बनाएं जिसका आकार (n+1) x (W+1) हो।
2. प्रारंभिक स्थिति: यदि W = 0 या n = 0, तो dp[i][w] = 0।
3. प्रत्येक वस्तु के लिए:
   a. यदि वर्तमान वस्तु का भार बैग की क्षमता से अधिक है, तो इसे छोड़ दें: 
      dp[i][w] = dp[i-1][w]
   b. अन्यथा, दो संभावनाओं में से अधिकतम चुनें:
      dp[i][w] = max(val[i-1] + dp[i-1][w - wt[i-1]], dp[i-1][w])
4. अंतिम उत्तर dp[n][W] में मिलेगा।

0/1 नैपसैक का उदाहरण (Example of 0/1 Knapsack Problem)

मान लीजिए कि हमें निम्नलिखित वस्तुएं दी गई हैं:

यदि बैग की क्षमता W = 5 है, तो अधिकतम मूल्य 90 होगा, जिसमें वस्तुएं (2,4) सम्मिलित की जाएँगी।

0/1 नैपसैक एल्गोरिदम की समय जटिलता (Time Complexity of 0/1 Knapsack)

• समय जटिलता: O(n × W) (डायनेमिक प्रोग्रामिंग तालिका भरने के कारण)
• स्थान जटिलता: O(n × W) (2D टेबल स्टोरेज के कारण)

0/1 नैपसैक की अनुप्रयोग (Applications of 0/1 Knapsack Problem)

• संसाधन आवंटन (Resource Allocation)
• पोर्टफोलियो ऑप्टिमाइज़ेशन (Portfolio Optimization)
• बैकपैकिंग और स्टोरेज प्लानिंग
• कंप्यूटर नेटवर्क में डेटा पैकेट शेड्यूलिंग

निष्कर्ष

0/1 नैपसैक समस्या एक महत्वपूर्ण ऑप्टिमाइज़ेशन समस्या है जो कई व्यावहारिक अनुप्रयोगों में उपयोग की जाती है। डायनेमिक प्रोग्रामिंग का उपयोग करके इसे O(n × W) समय में हल किया जा सकता है।