কম্পিউটার

C++ এ একটি অ্যারের ন্যূনতম সমন্বয় খরচ খুঁজুন


ধারণা

ধনাত্মক পূর্ণসংখ্যার একটি প্রদত্ত অ্যারের সাপেক্ষে, আমরা অ্যারের প্রতিটি উপাদানকে প্রতিস্থাপন করি যাতে অ্যারের সংলগ্ন উপাদানগুলির মধ্যে পার্থক্য একটি প্রদত্ত লক্ষ্যের চেয়ে কম বা সমান হয়৷ এখন, আমাদের কাজটি সামঞ্জস্যের খরচ কমিয়ে আনা, সেটি হল নতুন এবং পুরাতন মূল্যবোধের মধ্যে পার্থক্যের যোগফল। সুতরাং, আমাদের মূলত Σ|A[i] – Anew ছোট করতে হবে [আমি]| যেখানে 0 ≤ i ≤ n-1, n কে A[] এবং Aনতুন এর আকার হিসাবে চিহ্নিত করা হয় [] লক্ষ্যের চেয়ে কম বা সমান সন্নিহিত পার্থক্য সহ অ্যারে হিসাবে চিহ্নিত করা হয়। ধরুন অ্যারের সমস্ত উপাদান ধ্রুবক 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নতুন [i]|যতটা সম্ভব শূন্যের কাছাকাছি হওয়া উচিত। এটাও উল্লেখ্য যে,

|A[i] – Aনতুন [i+1] ]| ≤ লক্ষ্য।

এখানে, এই সমস্যাটি ডায়নামিক প্রোগ্রামিং (DP) দ্বারা সমাধান করা যেতে পারে।

অনুমান করুন dp1[i][j] A[i] থেকে j পরিবর্তন করার জন্য ন্যূনতম সমন্বয় খরচ প্রতিনিধিত্ব করে, তারপর DP সম্পর্ক দ্বারা সংজ্ঞায়িত করা হয় –

dp1[i][j] =মিনিট{dp1[i - 1][k]} + |j ​​- A[i]|

সব k এর জন্য যে |k - j| ≤ লক্ষ্য

এই ক্ষেত্রে, 0 ≤ i ≤ n এবং 0 ≤ j ≤ M যেখানে n হল অ্যারের উপাদানগুলির সংখ্যা এবং M =100। সুতরাং, সমস্ত kvalue এইভাবে বিবেচনা করা হয় যাতে সর্বাধিক(j – লক্ষ্য, 0) ≤ k ≤ min(M, j + টার্গেট) শেষ পর্যন্ত, অ্যারের ন্যূনতম সমন্বয় খরচ হবে min{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

  1. C++ এ পরিবর্তিত অ্যারের ন্যূনতম মানের সর্বোচ্চ সম্ভাব্য মান খুঁজুন

  2. C++-এ অ্যারের ন্যূনতম এবং সর্বোচ্চ উপাদানগুলি খুঁজে পেতে পুনরাবৃত্তিমূলক প্রোগ্রাম

  3. C++ এ 3-D অ্যারেতে ন্যূনতম সমষ্টি পথ

  4. C++ এ প্রতিটি কার্টেসিয়ান স্থানাঙ্ক সংযোগ করার জন্য সর্বনিম্ন খরচ খুঁজে বের করার জন্য প্রোগ্রাম