0/1 डायनेमिक प्रोग्रामिंग उदाहरण का उपयोग करके नैप्सैक समस्या का समाधान

नैप्सैक समस्या क्या है?

RSI बस्ता समस्या यह एक क्लासिक संयोजनात्मक अनुकूलन समस्या है। एक सुपरमार्केट स्टोर n पैकेज (n ≤ 100)। पैकेज i एक चोर के पास क्षमता M (M ≤ 100) से अधिक भार नहीं हो सकता। कुल मूल्य को अधिकतम करने के लिए चोर को कौन से पैकेज ले जाने चाहिए?

इनपुट:

• अधिकतम वजन M और पैकेजों की संख्या n.
• भार W[i] और संगत मान V[i] की सरणी।

आउटपुट:

• क्षमता के भीतर प्राप्त की जा सकने वाली अधिकतम कुल कीमत।
• चोर को ठीक वही पैकेज लेने चाहिए।

नैपसैक एल्गोरिदम दो प्रसिद्ध प्रकारों में विभाजित होता है:

• 0/1 बस्ता समस्या इसे डायनामिक प्रोग्रामिंग द्वारा हल किया जाता है। प्रत्येक पैकेज या तो पूरा लिया जाता है या छोड़ दिया जाता है — कोई आंशिक भाग नहीं और कोई डुप्लिकेट नहीं।
• आंशिक बस्ता समस्या इसे एक लालची रणनीति द्वारा हल किया जाता है। यहाँ आप शेष क्षमता को भरने के लिए किसी भी पैकेज का एक अंश ले सकते हैं।

डायनेमिक प्रोग्रामिंग का उपयोग करके नैप्सैक समस्या को उदाहरण सहित कैसे हल करें

डिवाइड-एंड-कॉन्कर विधि किसी बड़ी समस्या को उपसमस्याओं में विभाजित करती है, और तब तक विभाजित करती रहती है जब तक कि प्रत्येक उपसमस्या सरल न हो जाए। दूसरी ओर, साधारण रिकर्सन अक्सर एक ही उपसमस्या को कई बार हल करता है और समय बर्बाद करता है।

नैपसैक डायनेमिक प्रोग्रामिंग का मूल विचार प्रत्येक हल किए गए उपसमस्या को एक तालिका में संग्रहीत करना है। बार-बार किए जाने वाले कॉल उत्तर को पुनः गणना करने के बजाय पढ़ते हैं, जिससे एक घातीय पुनरावृति बहुपद-समय कोड में परिवर्तित हो जाती है।

डायनेमिक प्रोग्रामिंग का उपयोग करके नैप्सैक समस्या को हल करें

डायनामिक प्रोग्रामिंग सॉल्यूशन डिजाइन करने के लिए, आपको चार चरणों का पालन करना होगा:

• सबसे पहले सबसे छोटी उपसमस्याओं को हल करें।
• एक ऐसी पुनरावृति विधि विकसित करें जो छोटे-छोटे उपसमस्याओं के उत्तरों से एक उपसमस्या का उत्तर तैयार करती हो।
• पुनरावृति विधि का उपयोग करके नीचे से ऊपर की ओर गणना की गई तालिका में उपसमस्याओं के उत्तर संग्रहित करें।
• पूरी तरह से भरी हुई तालिका से अंतिम उत्तर तैयार करें।

0/1 नैप्सैक समस्या का विश्लेषण करें

इष्टतम मान दो स्वतंत्र कारकों पर निर्भर करता है:

1. कितने पैकेज अभी भी विचाराधीन हैं?
2. बैग में अभी भी शेष वजन समा सकता है।

क्योंकि उद्देश्य फलन दो राशियों पर निर्भर करता है, इसलिए विकल्पों की तालिका द्वि-आयामी होनी चाहिए। B[i][j] वजन सीमा j के साथ पैकेज {1, …, i} में से चयन करते समय अधिकतम मान को निरूपित करें।

• अंतिम उत्तर यह है B[n][M]क्षमता M के अंतर्गत सभी n पैकेजों में सर्वश्रेष्ठ कुल मूल्य।
• चयनित कुल भार हमेशा वर्तमान क्षमता द्वारा सीमित होता है: B[i][j] ≤ j.

उदाहरण: यदि B[4][10] = 8 है, तो क्षमता 10 के अंतर्गत पहले चार पैकेजों का सर्वोत्तम कुल वजन 8 है। उन चार पैकेजों में से कुछ को छोड़ा जा सकता है।

B[i][j] की गणना करने का सूत्र

• W[i], V[i] पैकेज i का भार और मूल्य क्रमशः {1, …, n} में है।
• M यह वह अधिकतम भार है जिसे बैकपैक वहन कर सकता है।

एक पैकेज के साथ आधार मामला: प्रत्येक क्षमता j ≥ W[1] के लिए:

B[1][j] = W[1]

सामान्य स्थिति के लिए, यह तय करें कि पैकेज i को क्षमता j के अंतर्गत शामिल किया जाए या नहीं:

• यदि पैकेज i है को छोड़ दिया, B[i][j] क्षमता j के अंतर्गत पैकेज {1, …, i-1} का उपयोग करके सर्वोत्तम मान के बराबर है:

B[i][j] = B[i - 1][j]

• यदि पैकेज i है लिया (केवल तभी अनुमत जब W[i] ≤ j), B[i][j] बराबर V[i] प्लस पैकेज {1, …, i-1} से क्षमता j – W[i] के अंतर्गत सर्वोत्तम मान:

B[i][j] = V[i] + B[i - 1][j - W[i]]

दोनों उम्मीदवारों में से बड़े उम्मीदवार को चुनें।

डायनेमिक प्रोग्रामिंग का आधार

दोनों मामलों को मिलाने से पूर्ण पुनरावृत्ति प्राप्त होती है:

B[i][j] = max(B[i - 1][j], V[i] + B[i - 1][j - W[i]])

मूल स्थिति यह है B[0][j] = 0 प्रत्येक j के लिए, क्योंकि शून्य पैकेज क्षमता की परवाह किए बिना शून्य मूल्य देते हैं।

विकल्पों की तालिका की गणना करें

पुनरावृति विधि का उपयोग करके B का निर्माण करें। एक बार B भर जाने पर, वही तालिका आगे की प्रक्रिया को संचालित करती है। tracई-बैक जो चयनित पैकेजों का पुनर्निर्माण करता है। तालिका B में n + 1 पंक्तियाँ और M + 1 स्तंभ हैं:

• पंक्ति 0 आधार स्थिति है, जो शून्यों से भरी हुई है।
• पंक्ति 0 का उपयोग करके पंक्ति 1 की गणना करें, पंक्ति 1 का उपयोग करके पंक्ति 2 की गणना करें, और पंक्ति n पूरी होने तक जारी रखें।

विकल्पों की तालिका

Trace

एक बार B पूरा हो जाने पर, इस पर ध्यान केंद्रित करें B[n][M]क्षमता M वाले सभी n पैकेजों के लिए इष्टतम कुल मूल्य।

• If B[n][M] = B[n-1][M]पैकेज n का चयन नहीं किया गया, इसलिए जारी रखें tracबी[एन-1][एम] से।
• If B[n][M] ≠ B[n-1][M]पैकेज n का चयन हो गया है, इसलिए जारी रखें tracबी[एन-1][एम – डब्ल्यू[एन]] से।

तालिका की पंक्ति 0 तक पहुंचने तक इसे दोहराएं।

चयनित पैकेजों को खोजने के लिए विकल्पों की तालिका देखने का एल्गोरिदम

नोट: जब भी B[i][j] = B[i-1][j]पैकेज i का चयन नहीं किया गया है। मान B[n][M] यह थैले में पैक की गई कुल इष्टतम कीमत है।

के लिए कदम tracचयनित पैकेजों को शामिल करना:

• चरण १: i = n, j = M से शुरू करें।
• चरण १: कॉलम j को नीचे से ऊपर की ओर तब तक स्कैन करें जब तक आपको पंक्ति i न मिल जाए जहाँ B[i][j] > B[i-1][j] हो। पैकेज i को चयनित के रूप में चिह्नित करें: Select[i] = true.
• चरण १: j = j – W[i] को अपडेट करें। यदि j > 0 है, तो चरण 2 पर वापस जाएँ, अन्यथा चरण 4 पर जाएँ।
• चरण १: चयनित के रूप में चिह्नित प्रत्येक पैकेज को प्रिंट करें।

Java Code

निम्नलिखित Java यह विधि B[][] को नीचे से ऊपर की ओर भरती है, निरीक्षण के लिए तालिका प्रिंट करती है, और फिर tracचयनित पैकेज।

public void knapsackDyProg(int W[], int V[], int M, int n) {
    int B[][] = new int[n + 1][M + 1];

    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= M; j++) {
            B[i][j] = 0;
        }

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= M; j++) {
            B[i][j] = B[i - 1][j];

            if ((j >= W[i - 1]) && (B[i][j] < B[i - 1][j - W[i - 1]] + V[i - 1])) {
                B[i][j] = B[i - 1][j - W[i - 1]] + V[i - 1];
            }

            System.out.print(B[i][j] + " ");
        }
        System.out.print("\n");
    }

    System.out.println("Max Value:\t" + B[n][M]);
    System.out.println("Selected Packs: ");

    int j = M;
    while (n != 0) {
        if (B[n][j] != B[n - 1][j]) {
            System.out.println("\tPackage " + n + " with W = " + W[n - 1] + " and Value = " + V[n - 1]);
            j = j - W[n - 1];
        }
        n--;
    }
}

फ़ंक्शन knapsackDyProg() Java

कोड का स्पष्टीकरण:

1. तालिका आवंटित करें B[][] और प्रत्येक सेल को 0 से इनिशियलाइज़ करें।
2. पिछले अनुभाग में दिए गए पुनरावृति नियम का उपयोग करके B[][] को नीचे से ऊपर की ओर भरें।
3. प्रत्येक सेल को “पैकेज i छोड़ें” मान से प्रारंभ करें B[i-1][j].
4. यदि पैकेज i का चयन करना संभव है और इससे बेहतर मूल्य प्राप्त होता है, तो सेल को ओवरराइट कर दें।
5. Tracपंक्ति n से चयनित वस्तुओं को वापस पंक्ति 0 में ले जाएं।
6. जब भी पैकेज n का चयन किया जाता है, शेष क्षमता को घटा दें। W[n-1].

सुधार नोट: मूल अंश परिवर्तित पैरामीटर M पढ़ते हुए B[n][M]ऊपर दिए गए सुरक्षित संस्करण में एक अलग कर्सर का उपयोग किया गया है। j के लिए trace.

RSI Java ड्राइवर दो हल किए गए उदाहरणों पर एल्गोरिदम चलाता है:

public void run() {
    // First Example
    // int W[] = new int[]{3, 4, 5, 9, 4};
    // int V[] = new int[]{3, 4, 4, 10, 4};
    // int M = 11;

    // Second Example
    int W[] = new int[]{12, 2, 1, 1, 4};
    int V[] = new int[]{4, 2, 1, 2, 10};
    int M = 15;

    int n = V.length;
    knapsackDyProg(W, V, M, n);
}

पहले उदाहरण का आउटपुट:

0 0 0 3 3 3 3 3 3 3 3 3
0 0 0 3 4 4 4 7 7 7 7 7
0 0 0 3 4 4 4 7 7 8 8 8
0 0 0 3 4 4 4 7 7 10 10 10
0 0 0 3 4 4 4 7 8 10 10 11
Max Value:	11
Selected Packs:
	Package 5 with W = 4 and Value = 4
	Package 2 with W = 4 and Value = 4
	Package 1 with W = 3 and Value = 3

दूसरे उदाहरण का आउटपुट:

0 0 0 0 0 0 0 0 0 0 0 0 4 4 4 4
0 0 2 2 2 2 2 2 2 2 2 2 4 4 6 6
0 1 2 3 3 3 3 3 3 3 3 3 4 5 6 7
0 2 3 4 5 5 5 5 5 5 5 5 5 6 7 8
0 2 3 4 10 12 13 14 15 15 15 15 15 15 15 15
Max Value:	15
Selected Packs:
	Package 5 with W = 4 and Value = 10
	Package 4 with W = 1 and Value = 2
	Package 3 with W = 1 and Value = 1
	Package 2 with W = 2 and Value = 2

0/1 नैपसैक की समय और स्थान जटिलता

• समय जटिलता: O(n · M) — दो नेस्टेड लूप M+1 क्षमता अवस्थाओं में n वस्तुओं को स्कैन करते हैं।
• स्थानिक जटिलता: पूरी तालिका के लिए O(n · M), जिसे की द्वारा O(M) में बदला जा सकता है।ping केवल पिछली पंक्ति जब tracई-बैक की आवश्यकता नहीं है।

रनटाइम है छद्म-बहुपदM के मान में बहुपद होता है, लेकिन M को एन्कोड करने के लिए उपयोग किए जाने वाले बिट्स में घातांकीय होता है। यही कारण है कि 0/1 नैपसैक NP-कठिन बना रहता है, भले ही डायनामिक प्रोग्रामिंग व्यवहार में कुशल हो।

0/1 नैपसैक समस्या के अनुप्रयोग

• वजन सीमा के भीतर माल की लोडिंग, कंटेनर पैकिंग और वेयरहाउस में माल की ढुलाई।
• निवेश परियोजनाओं में बजट आवंटन में निश्चित लागत और अपेक्षित प्रतिफल को शामिल किया गया है।
• विनिर्माण में कटिंग-स्टॉक की समस्याएँ होती हैं जिनके कारण अलग-अलग टुकड़ों को विभाजित नहीं किया जा सकता है।
• मर्कल-हेलमैन जैसी क्रिप्टोग्राफी योजनाएं जो नैपसैक कठोरता पर आधारित हैं।
• क्लाउड कंप्यूटिंग में संसाधन-बाधित शेड्यूलिंग और सीपीयू टास्क प्लेसमेंट।
• एक निश्चित फीचर बजट के तहत मशीन लर्निंग में फीचर चयन।

अक्सर पूछे जाने वाले प्रश्न