- Trending Categories
- Data Structure
- Networking
- RDBMS
- Operating System
- Java
- iOS
- HTML
- CSS
- Android
- Python
- C Programming
- C++
- C#
- MongoDB
- MySQL
- Javascript
- PHP

- Selected Reading
- UPSC IAS Exams Notes
- Developer's Best Practices
- Questions and Answers
- Effective Resume Writing
- HR Interview Questions
- Computer Glossary
- Who is Who

With respect of a given array of positive integers, we replace each element in the array so that the
difference between adjacent elements in the array is either less than or equal to a given target.
Now, our task to minimize the adjustment cost, that is the sum of differences between new and old
values. So, we basically need to minimize Σ|A[i] – A_{new}[i]| where 0 ≤ i ≤ n-1, n is denoted as size of A[] and A_{new}[] is denoted as the array with adjacent difference less than or equal to target. Let all elements of the array is smaller than constant M = 100.

arr = [56, 78, 53, 62, 40, 7, 26, 61, 50, 48], target = 20

Minimum adjustment cost is 35

For minimizing the adjustment cost Σ|A[i] – A_{new}[i]|, for all index i in the array, we remember that |A[i] – A_{new}[i]|should be as close to zero as possible. It should be noted that also,

|A[i] – A_{new}[i+1] ]| ≤ Target.

Here, this problem can be solved by dynamic programming(DP).

Assume dp1[i][j] represents minimal adjustment cost on changing A[i] to j, then the DP relation is defined by –

dp1[i][j] = min{dp1[i - 1][k]} + |j - A[i]|

for all k's such that |k - j| ≤ target

In this case, 0 ≤ i ≤ n and 0 ≤ j ≤ M where n is number of elements in the array and M = 100. So, all k values are considered in this way such that max(j – target, 0) ≤ k ≤ min(M, j + target) At last, the minimum adjustment cost of the array will be min{dp1[n – 1][j]} for all 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

- Related Questions & Answers
- Find minimum adjustment cost of an array in Python
- Find minimum cost to buy all books in C++
- Minimum Cost For Tickets in C++
- C Program for Minimum Cost Path
- Find the maximum cost of an array of pairs choosing at most K pairs in C++
- Minimum Cost to Connect Sticks in C++
- Minimum Cost to Merge Stones in C++
- Program to find the minimum (or maximum) element of an array in C++
- Find minimum number of merge operations to make an array palindrome in C++
- Minimum Cost Polygon Triangulation
- Find minimum in an array without using Relational Operators in C++
- Maximum and minimum of an array using minimum number of comparisons in C
- C# program to find maximum and minimum element in an array
- Find minimum operations needed to make an Array beautiful in C++
- Find indexes of multiple minimum value in an array in JavaScript

Advertisements