ধারণা
ধনাত্মক পূর্ণসংখ্যার একটি প্রদত্ত অ্যারের সাপেক্ষে, আমরা অ্যারের প্রতিটি উপাদানকে প্রতিস্থাপন করি যাতে অ্যারের সংলগ্ন উপাদানগুলির মধ্যে পার্থক্য একটি প্রদত্ত লক্ষ্যের চেয়ে কম বা সমান হয়৷ এখন, আমাদের কাজটি সামঞ্জস্যের খরচ কমিয়ে আনা, সেটি হল নতুন এবং পুরাতন মূল্যবোধের মধ্যে পার্থক্যের যোগফল। সুতরাং, আমাদের মূলত Σ|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
