अवधारणा
धनात्मक पूर्णांकों की दी गई सरणी के संबंध में, हम सरणी में प्रत्येक तत्व को प्रतिस्थापित करते हैं ताकि सरणी में आसन्न तत्वों के बीच का अंतर दिए गए लक्ष्य से कम या बराबर हो। अब, हमारा कार्य समायोजन लागत को न्यूनतम करना है, जो नए और पुराने मानों के बीच अंतर का योग है। तो, हमें मूल रूप से Σ|A[i] – A_new[i]| को न्यूनतम करना है जहां 0 ≤ i ≤ n-1, n को A[] के आकार के रूप में दर्शाया गया है और A_new[] को आसन्न अंतर लक्ष्य से कम या बराबर वाली सरणी के रूप में दर्शाया गया है। मान लें कि सरणी के सभी तत्व स्थिरांक M = 100 से छोटे हैं।
इनपुट
arr = [56, 78, 53, 62, 40, 7, 26, 61, 50, 48], target = 20
आउटपुट
न्यूनतम समायोजन लागत 35 है
विधि
समायोजन लागत Σ|A[i] – A_new[i]| को न्यूनतम करने के लिए, सभी सूचकांक i के लिए सरणी में, हम याद रखते हैं कि |A[i] – A_new[i]| शून्य के जितना संभव हो उतना करीब होना चाहिए। यह ध्यान दिया जाना चाहिए कि भी,
|A[i] – A_new[i+1] | ≤ लक्ष्य।
यहां, इस समस्या को डायनामिक प्रोग्रामिंग (DP) द्वारा हल किया जा सकता है।
मान लें dp1[i][j] A[i] को j में बदलने पर न्यूनतम समायोजन लागत दर्शाता है, तो DP संबंध द्वारा परिभाषित है -
dp1[i][j] = min{dp1[i - 1][k]} + |j - A[i]|
सभी k के लिए जैसे कि |k - j| ≤ लक्ष्य
इस मामले में, 0 ≤ i ≤ n और 0 ≤ j ≤ M जहां n सरणी में तत्वों की संख्या है और M = 100। तो, सभी k मानों पर इस तरह विचार किया जाता है कि max(j - लक्ष्य, 0) ≤ k ≤ min(M, j + लक्ष्य) अंत में, सरणी की न्यूनतम समायोजन लागत min{dp1[n - 1][j]} होगी सभी 0 ≤ j ≤ M के लिए।
उदाहरण
// सरणी की न्यूनतम समायोजन लागत ढूंढने के लिए C++ प्रोग्राम #include <bits/stdc++.h> using namespace std; #define M1 100 // सरणी की न्यूनतम समायोजन लागत ढूंढने के लिए फ़ंक्शन दिखाता है int minAdjustmentCost(int A1[], int n1, int target1){ // dp1[i][j] A1[i] को j में बदलने पर न्यूनतम समायोजन लागत संग्रहीत करता है int dp1[n1][M1 + 1]; // सरणी के पहले तत्व को अलग से संभालें for (int j = 0; j <= M1; j++) dp1[0][j] = abs(j - A1[0]); // सरणी के शेष तत्वों के लिए करें for (int i = 1; i < n1; i++){ // अब A1[i] को j से प्रतिस्थापित करें और न्यूनतम समायोजन // लागत dp1[i][j] की गणना करें for (int j = 0; j <= M1; j++){ // हम न्यूनतम समायोजन लागत को INT_MAX से प्रारंभ करते हैं dp1[i][j] = INT_MAX; // हम सभी k पर विचार करते हैं जैसे कि k >= max(j - target1, 0) और // k <= min(M1, j + target1) और न्यूनतम लेते हैं for (int k = max(j-target1,0); k <= min(M1,j+target1); k++) dp1[i][j] = min(dp1[i][j], dp1[i - 1][k] + abs(A1[i] -j)); } } // अब dp टेबल की अंतिम पंक्ति से न्यूनतम मान लौटाएं int res1 = INT_MAX; for (int j = 0; j <= M1; j++) res1 = min(res1, dp1[n1 - 1][j]); return res1; } // उपरोक्त फ़ंक्शन का परीक्षण करने के लिए ड्राइवर प्रोग्राम int main(){ int arr1[] = {56, 78, 53, 62, 40, 7, 26, 61, 50, 48}; int n1 = sizeof(arr1) / sizeof(arr1[0]); int target1 = 20; cout << "न्यूनतम समायोजन लागत है " << minAdjustmentCost(arr1, n1, target1) << endl; return 0; }
आउटपुट
न्यूनतम समायोजन लागत है 35
