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

Java

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 :)
 



Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
Abhishek
Guest

can you please expalin me as i’m finding difficulty understanding it.
dp[i][j] = min{dp[i – 1][k]} + |j – A[i]| for all k’s such that |k – j| <= target