C++ में किसी सरणी की न्यूनतम समायोजन लागत ज्ञात करें

अवधारणा

सकारात्मक पूर्णांकों के दिए गए सरणी के संबंध में, हम सरणी में प्रत्येक तत्व को प्रतिस्थापित करते हैं ताकि सरणी में आसन्न तत्वों के बीच का अंतर किसी दिए गए लक्ष्य से कम या बराबर हो। अब, समायोजन लागत को कम करने का हमारा कार्य, वह है नए और पुराने मूल्यों के बीच अंतर का योग। इसलिए, हमें मूल रूप से Σ|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

आउटपुट

Minimum adjustment cost is 35

विधि

समायोजन लागत को कम करने के लिए Σ|A[i] – A_नया [i]|, सरणी में सभी अनुक्रमणिका i के लिए, हमें याद है कि |A[i] – A_new [i]|जितना संभव हो शून्य के करीब होना चाहिए। यह भी ध्यान दिया जाना चाहिए कि,

|ए[i] - ए<उप>नया [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। तो, सभी kvalues ​​​​इस तरह से माना जाता है कि max(j – target, 0) ≤ k ≤ मिनट (एम, जे + लक्ष्य) अंत में, सरणी की न्यूनतम समायोजन लागत न्यूनतम होगी {dp1[n - 1][j]} सभी 0 j ≤ M.

उदाहरण

// C++ program to find minimum adjustment cost of an array
#include <bits/stdc++.h>
using namespace std;
#define M1 100
//Shows function to find minimum adjustment cost of an array
int minAdjustmentCost(int A1[], int n1, int target1){
   // dp1[i][j] stores minimal adjustment cost on changing
   // A1[i] to j
   int dp1[n1][M1 + 1];
   // Tackle first element of array separately
   for (int j = 0; j <= M1; j++)
      dp1[0][j] = abs(j - A1[0]);
   // Perform for rest elements of the array
   for (int i = 1; i < n1; i++){
      // Now replace A1[i] to j and calculate minimal adjustment
      // cost dp1[i][j]
      for (int j = 0; j <= M1; j++){
         // We initialize minimal adjustment cost to INT_MAX
         dp1[i][j] = INT_MAX;
         // We consider all k such that k >= max(j - target1, 0)
         and
         // k <= min(M1, j + target1) and take minimum
      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));
      }
   }
   //Now return minimum value from last row of dp table
   int res1 = INT_MAX;
   for (int j = 0; j <= M1; j++)
      res1 = min(res1, dp1[n1 - 1][j]);
   return res1;
}
// Driver Program to test above functions
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 << "Minimum adjustment cost is "
   << minAdjustmentCost(arr1, n1, target1) << endl;
   return 0;
}

आउटपुट

Minimum adjustment cost is 35