Determine Minimal Adjustment Cost of an Array

Write an algorithm to replace each element in an array of positive integers such that the difference between adjacent elements in the array is less than or equal to a given target. We need to minimize the adjustment cost which is the sum of differences between new and old values.

In other words, minimize ∑|A[i] – Anew[i]|, where 0 <= i <= n-1, n is size of A[] and Anew[] is the array with adjacent difference less that or equal to target.


 

For example,


Input: arr = [1, 3, 0, 3], target = 1
Output: Minimum adjustment cost is 3

One of the possible solutions is [2, 3, 2, 3]

 
Input: arr = [55, 77, 52, 61, 39, 6, 25, 60, 49, 47], target = 10
Output: Minimum adjustment cost is 75

One of the possible solutions is [55, 62, 52, 49, 39, 29, 30, 40, 49, 47]

 
Input: arr = [2, 3, 2, 3], target = 1
Output: Minimum adjustment cost is 0
All adjacent elements in the input array are already less than equal to given target

 


 

In order to minimize the adjustment cost ∑|A[i] – Anew[i]| for all index i in the array,
|A[i] – Anew[i]| should be as close to 0 as possible. Also, |A[i] – Anew[i+1] ]| <= Target.

 
We can use Dynamic Programming to solve this problem. Let T[i][j] defines minimal adjustment cost on changing A[i] to j, then the DP relation is defined by –

T[i][j] = min{T[i - 1][k]} + |j - A[i]|     for all k's such that |k - j| <= target

Here, 0 <= i < n and 0 <= j <= M where n is number of elements in the array. We have to consider all k such that max(j – target, 0) <= k <= min(M, j + target). Finally the minimum adjustment cost of the array will be min{T[n – 1][j]} for all 0 <= j <= M.

C

Download   Run Code

Output:

The minimal adjustment cost is 75

 
Author: Aditya Goel

 
Thanks for reading.

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding :)
 


Get great deals at Amazon




Leave a Reply

Notify of
avatar
wpDiscuz