Knapsack Problem in Hindi | नैपसैक समस्या क्या है?

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

नैपसैक समस्या (Knapsack Problem) एक ऑप्टिमाइज़ेशन (Optimization) समस्या है, जिसमें दिए गए वस्तुओं (Items) के भार (Weight) और मूल्य (Value) के आधार पर एक निश्चित क्षमता वाले बैग (Knapsack) में अधिकतम मूल्य प्राप्त करना होता है। यह कंप्यूटर विज्ञान और ऑपरेशंस रिसर्च में एक महत्वपूर्ण समस्या है।

नैपसैक समस्या के प्रकार (Types of Knapsack Problem)

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

इस समस्या में प्रत्येक वस्तु को केवल एक बार लिया जा सकता है। इसका हल डायनामिक प्रोग्रामिंग (Dynamic Programming) का उपयोग करके निकाला जाता है।

Knapsack(W, wt[], val[], n)
    if n == 0 or W == 0:
        return 0
    if wt[n-1] > W:
        return Knapsack(W, wt, val, n-1)
    else:
        return max(
            val[n-1] + Knapsack(W - wt[n-1], wt, val, n-1),
            Knapsack(W, wt, val, n-1)
        )

फ्रैक्शनल नैपसैक समस्या (Fractional Knapsack Problem)

इस समस्या में वस्तुओं को आंशिक रूप से बैग में डाला जा सकता है। यह ग्रीडी एल्गोरिदम (Greedy Algorithm) द्वारा हल किया जाता है।

FractionalKnapsack(W, items[], n)
    1. Sort items in decreasing order of value/weight ratio
    2. Initialize totalValue = 0
    3. for each item in sorted list:
        if item can fit completely:
            add it to knapsack
            totalValue += item value
        else:
            add fraction of item to knapsack
            totalValue += fraction value
    4. return totalValue

नैपसैक समस्या का उदाहरण (Example of Knapsack Problem)

माना कि हमारे पास 3 वस्तुएं हैं:

यदि बैग की क्षमता W = 50 है, तो:

• 0/1 Knapsack: अधिकतम मूल्य 220 होगा।
• Fractional Knapsack: अधिकतम मूल्य 240 होगा।

नैपसैक समस्या की समय जटिलता (Time Complexity of Knapsack Problem)

• 0/1 Knapsack (डायनामिक प्रोग्रामिंग): O(nW)
• Fractional Knapsack (ग्रीडी एल्गोरिदम): O(n log n)

नैपसैक समस्या के अनुप्रयोग (Applications of Knapsack Problem)

• रिसोर्स एलोकेशन (Resource Allocation)
• फ्रैक्शनल स्टॉक इन्वेस्टमेंट
• डाटा कम्प्रेशन (Data Compression)
• बैग पैकिंग ऑप्टिमाइज़ेशन

निष्कर्ष

नैपसैक समस्या एक महत्वपूर्ण ऑप्टिमाइज़ेशन समस्या है जो वास्तविक जीवन की कई समस्याओं में उपयोग की जाती है। 0/1 Knapsack समस्या डायनामिक प्रोग्रामिंग से हल की जाती है, जबकि Fractional Knapsack समस्या ग्रीडी एल्गोरिदम से हल होती है।