Find minimum adjustment cost of an array - GeeksforGeeks
http://www.lintcode.com/en/problem/minimum-adjustment-cost/
Given an array of positive integers, replace each element in the array 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, that is the sum of differences between new and old values. We basically need to 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.
Assume all elements of the array is less than constant M = 100.
http://www.cnblogs.com/EdwardLiu/p/4385819.html
http://www.jiuzhang.com/solutions/minimum-adjustment-cost/
Read full article from Find minimum adjustment cost of an array - GeeksforGeeks
http://www.lintcode.com/en/problem/minimum-adjustment-cost/
Given an array of positive integers, replace each element in the array 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, that is the sum of differences between new and old values. We basically need to 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.
Assume all elements of the array is less than constant M = 100.
http://www.cnblogs.com/EdwardLiu/p/4385819.html
http://www.jiuzhang.com/solutions/minimum-adjustment-cost/
定义res[i][j] 表示前 i个number with 最后一个number是j，这样的minimum adjusting cost
如果第i-1个数是j, 那么第i-2个数只能在[lowerRange, UpperRange]之间，lowerRange=Math.max(0, j-target), upperRange=Math.min(99, j+target),
这样的话，transfer function可以写成：
for (int p=lowerRange; p<= upperRange; p++) {
res[i][j] = Math.min(res[i][j], res[i-1][p] + Math.abs(j-A.get(i-1)));
}
6 public int MinAdjustmentCost(ArrayList<Integer> A, int target) { 7 // write your code here 8 int[][] res = new int[A.size()+1][100]; 9 for (int j=0; j<=99; j++) { 10 res[0][j] = 0; 11 } 12 for (int i=1; i<=A.size(); i++) { 13 for (int j=0; j<=99; j++) { 14 res[i][j] = Integer.MAX_VALUE; 15 int lowerRange = Math.max(0, j-target); 16 int upperRange = Math.min(99, j+target); 17 for (int p=lowerRange; p<=upperRange; p++) { 18 res[i][j] = Math.min(res[i][j], res[i-1][p]+Math.abs(j-A.get(i-1))); 19 } 20 } 21 } 22 int result = Integer.MAX_VALUE; 23 for (int j=0; j<=99; j++) { 24 result = Math.min(result, res[A.size()][j]); 25 } 26 return result; 27 }https://segmentfault.com/a/1190000004950954
public int MinAdjustmentCost(ArrayList<Integer> A, int target) {
int n = A.size();
int max = 0;
for (int i = 0; i < n; i++) {
max = Math.max(max, A.get(i));
}
int[][] d = new int[n][max+1];
for (int j = 0; j <= max; j++) {
d[0][j] = Math.abs(A.get(0) - j);
}
int curMin = 0;
for (int i = 1; i < n; i++) {
curMin = Integer.MAX_VALUE;
for (int j = 0; j <= max; j++) {
d[i][j] = Integer.MAX_VALUE;
for (int k = Math.max(0, j-target); k <= Math.min(max, j+target); k++) {
d[i][j] = Math.min(d[i][j], d[i-1][k] + Math.abs(A.get(i)-j));
curMin = Math.min(curMin, d[i][j]);
}
}
}
return curMin;
} Backpack DP problem. Three for loops.
- For each A[i]
- For each possible value curV (1 … 100) that A[i] could be adjusted to.
- For each valid value lastV (1 … 100) that A[i – 1] could be adjusted to (|curV – lastV| < target). Calculate the sum of local adjustment cost:|curV – A[i]| and the accumulative min adjustment cost for A[0 … i] saved in minCost[lastV]
public int MinAdjustmentCost(ArrayList<Integer> A, int target) {
// write your code here
if (A == null || A.size() == 0) {
return 0;
}
int curMinCost[] = new int[101]; //curMinCost[v]: the min cost in A[0..i] if A[i] is changed to v
int lastMinCost[] = new int[101]; //lastMinCost[v]: the min cost in A[0..i - 1] if A[i - 1] is changed to v
//initialize
for (int v = 1; v <= 100; v++) {
curMinCost[v] = Math.abs(v - A.get(0));
}
for (int i = 1; i < A.size(); i++) {
System.arraycopy(curMinCost, 1, lastMinCost, 1, 100);
for (int curV = 1; curV <= 100; curV++) {
curMinCost[curV] = Integer.MAX_VALUE;
for (int lastV = 1; lastV <= 100; lastV++) {
if (Math.abs(curV - lastV) > target) {
continue;
}
curMinCost[curV] = Math.min(curMinCost[curV], lastMinCost[lastV] + Math.abs(curV - A.get(i)));
}
}
}
int min = Integer.MAX_VALUE;
for (int v = 1; v <= 100; v++) {
min = Math.min(min, curMinCost[v]);
}
return min;
}
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 zero as possible. Also, |A[i] – Anew[i+1] ]| <= Target.
This problem can be solved by dynamic programming.
Let dp[i][j] defines minimal adjustment cost on changing A[i] to j, then the DP relation is defined by –
dp[i][j] = min{dp[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 and M = 100. 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{dp[n – 1][j]} for all 0 <= j <= M.
int minAdjustmentCost(int A[], int n, int target){ // dp[i][j] stores minimal adjustment cost on changing // A[i] to j int dp[n][M + 1]; // handle first element of array seperately for (int j = 0; j <= M; j++) dp[0][j] = abs(j - A[0]); // do for rest elements of the array for (int i = 1; i < n; i++) { // replace A[i] to j and calculate minimal adjustment // cost dp[i][j] for (int j = 0; j <= M; j++) { // initialize minimal adjustment cost to INT_MAX dp[i][j] = INT_MAX; // consider all k such that k >= max(j - target, 0) and // k <= min(M, j + target) and take minimum for (int k = max(j-target,0); k <= min(M,j+target); k++) dp[i][j] = min(dp[i][j], dp[i - 1][k] + abs(A[i] - j)); } } // return minimum value from last row of dp table int res = INT_MAX; for (int j = 0; j <= M; j++) res = min(res, dp[n - 1][j]); return res;}