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

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

बस्ता समस्या एल्गोरिथ्म संयोजन विज्ञान में एक बहुत ही उपयोगी समस्या है। सुपरमार्केट में n पैकेज हैं (n ≤ 100) पैकेज i का वजन W[i] ≤ 100 और मूल्य V[i] ≤ 100 है। एक चोर सुपरमार्केट में घुस जाता है, चोर M (M ≤ 100) से अधिक वजन नहीं उठा सकता। यहाँ हल की जाने वाली समस्या यह है: चोर कौन से पैकेज ले जाएगा ताकि सबसे अधिक मूल्य प्राप्त हो?

इनपुट:

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

आउटपुट:

  • क्षमता में मूल्य और संगत भार को अधिकतम करें।
  • चोर कौन से पैकेट ले जाएगा।

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

  • डायनेमिक प्रोग्रामिंग का उपयोग करके 0/1 नैप्सैक समस्या। इस नैप्सैक एल्गोरिथम प्रकार में, प्रत्येक पैकेज लिया जा सकता है या नहीं लिया जा सकता है। इसके अलावा, चोर लिए गए पैकेज की आंशिक मात्रा नहीं ले सकता है या एक पैकेज को एक से अधिक बार नहीं ले सकता है। इस प्रकार को डायनेमिक प्रोग्रामिंग दृष्टिकोण द्वारा हल किया जा सकता है।
  • भिन्नात्मक नैप्सैक समस्या एल्गोरिथ्मइस प्रकार को लालची रणनीति द्वारा हल किया जा सकता है।

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

विभाजित-और-जीत रणनीति में, आप हल की जाने वाली समस्या को उप-समस्याओं में विभाजित करते हैं। उप-समस्याओं को आगे छोटी-छोटी उप-समस्याओं में विभाजित किया जाता है। यह कार्य तब तक जारी रहेगा जब तक आपको ऐसी उप-समस्याएँ न मिल जाएँ जिन्हें आसानी से हल किया जा सके। हालाँकि, इस तरह के विभाजन की प्रक्रिया में, आपको कई बार एक ही समस्या का सामना करना पड़ सकता है।

नैप्सैक डायनेमिक प्रोग्रामिंग का मूल विचार हल की गई उप-समस्याओं के समाधान को संग्रहीत करने के लिए एक तालिका का उपयोग करना है। यदि आप फिर से किसी उप-समस्या का सामना करते हैं, तो आपको इसे फिर से हल किए बिना केवल तालिका में समाधान लेना होगा। इसलिए, डायनेमिक प्रोग्रामिंग द्वारा डिज़ाइन किए गए एल्गोरिदम बहुत प्रभावी हैं।

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

डायनेमिक प्रोग्रामिंग द्वारा किसी समस्या को हल करने के लिए, आपको निम्नलिखित कार्य करने होंगे:

  • सबसे छोटी उपसमस्याओं का समाधान ढूंढें।
  • सबसे छोटी उपसमस्याओं के समाधान के माध्यम से उपसमस्या का समाधान बनाने के लिए सूत्र (या नियम) का पता लगाएं।
  • एक तालिका बनाएँ जो उप-समस्याओं के समाधान को संग्रहीत करती है। फिर प्राप्त सूत्र के अनुसार उप-समस्या के समाधान की गणना करें और तालिका में सहेजें।
  • हल की गई उपसमस्याओं से आप मूल समस्या का समाधान ढूंढते हैं।

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

डायनेमिक प्रोग्रामिंग का उपयोग करके 0/1 नैप्सैक समस्या का विश्लेषण करते समय, आप कुछ ध्यान देने योग्य बिंदु पा सकते हैं। नैप्सैक एल्गोरिदम का मूल्य दो कारकों पर निर्भर करता है:

  1. कितने पैकेजों पर विचार किया जा रहा है
  2. शेष वजन जो बस्ता संग्रहित कर सकता है।

इसलिए, आपके पास दो परिवर्तनीय मात्राएँ हैं।

डायनेमिक प्रोग्रामिंग के साथ, आपके पास उपयोगी जानकारी है:

  1. उद्देश्य फ़ंक्शन दो परिवर्तनीय मात्राओं पर निर्भर करेगा
  2. विकल्पों की तालिका एक 2-आयामी तालिका होगी।

यदि पैकेज {1, 2, …, i} में भार सीमा j के साथ चयन करके B[i][j] को कॉल करना अधिकतम संभव मान है।

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

उदाहरण के लिए: B[4][10] = 8. इसका मतलब है कि इष्टतम मामले में, चयनित पैकेजों का कुल वजन 8 है, जब चुनने के लिए 4 पहले पैकेज हैं (1 से 4 वें पैकेज) और बस्ते का अधिकतम वजन 10 है। यह आवश्यक नहीं है कि सभी 4 आइटम चुने जाएं।

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

इनपुट, आप परिभाषित करते हैं:

  • W[i], V[i] क्रमशः पैकेज i का वजन और मूल्य हैं, जिसमें i B[i][j] की गणना करने का सूत्र{1, …, एन}.
  • M वह अधिकतम भार है जिसे बस्ता उठा सकता है।

चुनने के लिए केवल 1 पैकेज होने की स्थिति में। आप प्रत्येक j के लिए B[1][j] की गणना करते हैं: जिसका अर्थ है कि बस्ते का अधिकतम वजन ≥ पहले पैकेज का वजन

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

भार सीमा j के साथ, पैकेज {1, 2, …, i – 1, i} के बीच सबसे बड़ा मान वाले इष्टतम चयन की दो संभावनाएँ होंगी:

  • यदि पैकेज i का चयन नहीं किया गया है, तो B[i][j] वजन सीमा j के साथ पैकेज {1, 2, …, i – 1} के बीच चयन करके अधिकतम संभव मान है। आपके पास है:
B[i][j] = B[i – 1][j]
  • यदि पैकेज i चुना जाता है (बेशक इस मामले पर तभी विचार करें जब W[i] ≤ j हो) तो B[i][j] पैकेज i के मान V[i] के बराबर है और अधिकतम मान वजन सीमा (j – W[i]) के साथ पैकेज {1, 2, …, i – 1} में से चयन करके प्राप्त किया जा सकता है। यानी, आपके पास जो मान है उसके संदर्भ में:
B[i][j] = V[i] + B[i – 1][j – W[i]]

B[i][j] के निर्माण के कारण, जो कि अधिकतम संभव मान है, B[i][j] उपरोक्त 2 मानों में से अधिकतम होगा।

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

इसलिए, आपको यह विचार करना होगा कि पैकेज i चुनना बेहतर है या नहीं। वहां से आपके पास निम्न प्रकार का पुनरावर्ती सूत्र है:

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

यह देखना आसान है कि B[0][j] = 0 पैकेज = 0 से चयन करके अधिकतम संभव मान है।

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

आप उपरोक्त पुनरावर्ती सूत्र के आधार पर विकल्पों की एक तालिका बनाते हैं। यह जाँचने के लिए कि क्या परिणाम सही हैं (यदि बिल्कुल सही नहीं हैं, तो आप उद्देश्य फ़ंक्शन B[i][j] का पुनर्निर्माण करते हैं)। उद्देश्य फ़ंक्शन B[i][j] और विकल्पों की तालिका के निर्माण के माध्यम से, आप ट्रेसिंग को उन्मुख करेंगे।

विकल्प B की तालिका में n + 1 पंक्तियाँ, M + 1 कॉलम शामिल हैं,

  • सबसे पहले, गतिशील प्रोग्रामिंग के आधार पर: पंक्ति 0 में सभी शून्य शामिल हैं।
  • पुनरावर्ती सूत्रों का उपयोग करते हुए, पंक्ति 0 की गणना करने के लिए पंक्ति 1 का उपयोग करें, पंक्ति 1 की गणना करने के लिए पंक्ति 2 का उपयोग करें, आदि... जब तक कि सभी पंक्तियों की गणना न हो जाए।
विकल्पों की तालिका की गणना करें
विकल्पों की तालिका

निशान

विकल्पों की तालिका की गणना करते समय, आप B[n][M] में रुचि रखते हैं जो कि भार सीमा M के साथ सभी n पैकेजों में चयन करते समय प्राप्त अधिकतम मूल्य है।

  • If बी[एन][एम] = बी[एन – 1][एम] तब पैकेज n का चयन नहीं किया जाता है, आप B[n – 1][M] का पता लगाते हैं।
  • If बी[एन][एम] ≠ बी[एन – 1][एम], आप देखते हैं कि इष्टतम चयन में पैकेज n और ट्रेस B[n – 1][M – W[n]] है।

विकल्पों की तालिका की पंक्ति 0 तक पहुंचने तक अनुरेखण जारी रखें।

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

नोट: यदि B[i][j] = B[i – 1][j], तो पैकेज i का चयन नहीं किया जाता है। B[n][W] बस्ते में डाले गए पैकेज का इष्टतम कुल मूल्य है।

अनुरेखण के लिए चरण:

  • चरण 1i = n से प्रारंभ करते हुए, j = M.
  • चरण 2: कॉलम j में नीचे से ऊपर देखें, आपको लाइन i मिलेगी जैसे कि B[i][j] > B[i – 1][j]। चयनित पैकेज i को चिह्नित करें: Select [i] = true;
  • चरण 3: j = B[i][j] – W[i]. यदि j > 0, तो चरण 2 पर जाएँ, अन्यथा चरण 4 पर जाएँ
  • चरण 4: चयनित पैकेजों को मुद्रित करने के लिए विकल्पों की तालिका के आधार पर।

Java कोड

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: ");
	
	while (n != 0) {
		if (B[n][M] != B[n - 1][M]) {
			System.out.println("\tPackage " + n + " with W = " + W[n - 1] + " and Value = " + V[n - 1]);
			
			M = M - W[n-1];
		}
		
		n--;
	}
}
फ़ंक्शन knapsackDyProg() Java

फ़ंक्शन knapsackDyProg() Java

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

  1. तालिका B[][] बनाएँ। प्रत्येक कक्ष के लिए डिफ़ॉल्ट मान 0 सेट करें।
  2. नीचे से ऊपर की ओर तरीके से टेबल B[][] बनाएँ। पुनर्प्राप्ति सूत्र के साथ विकल्पों की तालिका की गणना करें।
  3. B[i][j] की गणना करें। यदि आप पैकेज i का चयन नहीं करते हैं।
  4. फिर मूल्यांकन करें: यदि आप पैकेज i का चयन करते हैं, तो यह B[i][j] को रीसेट करने से अधिक फायदेमंद होगा।
  5. पंक्ति n से पंक्ति 0 तक तालिका का अनुरेखण करें।
  6. यदि आप पैकेज n चुनते हैं। एक बार पैकेज n का चयन करने के बाद, केवल वजन M - W[n - 1] जोड़ सकते हैं।


इस ट्यूटोरियल में, आपके पास दो उदाहरण हैं। यहाँ दो उदाहरणों के साथ उपरोक्त प्रोग्राम को चलाने के लिए जावा कोड दिया गया है:

public void run() {
	/*
	 * Pack and Weight - Value
	 */
	//int W[] = new int[]{3, 4, 5, 9, 4};
	int W[] = new int[]{12, 2, 1, 1, 4};
	
	//int V[] = new int[]{3, 4, 4, 10, 4};
	int V[] = new int[]{4, 2, 1, 2, 10};
	
	/*
	 * Max Weight
	 */
	//int M = 11;
	int M = 15;
	int n = V.length;
	
	/*
	 * Run the algorithm
	 */
	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