Khái niệm
Đối với một mảng các số nguyên dương nhất định, chúng tôi thay thế từng phần tử trong mảng để sự khác biệt giữa các phần tử liền kề trong mảng nhỏ hơn hoặc bằng một mục tiêu nhất định. tổng chênh lệch giữa giá trị mới và giá trị cũ. Vì vậy, về cơ bản chúng ta cần giảm thiểu Σ | A [i] - A new [i] | trong đó 0 ≤ i ≤ n-1, n được biểu thị là kích thước của A [] và A mới [] được biểu thị là mảng có hiệu số liền kề nhỏ hơn hoặc bằng đích. Cho tất cả các phần tử của mảng nhỏ hơn hằng số M =100.
Đầu vào
arr = [56, 78, 53, 62, 40, 7, 26, 61, 50, 48], target = 20
Đầu ra
Minimum adjustment cost is 35
Phương pháp
Để giảm thiểu chi phí điều chỉnh Σ | A [i] - A mới [i] |, đối với tất cả chỉ mục i trong mảng, chúng ta nhớ rằng | A [i] - A new [i] | phải càng gần 0 càng tốt. Cũng cần lưu ý rằng,
| A [i] - A mới [i + 1]] | ≤ Mục tiêu.
Ở đây, vấn đề này có thể được giải quyết bằng lập trình động (DP).
Giả sử dp1 [i] [j] đại diện cho chi phí điều chỉnh tối thiểu khi thay đổi A [i] thành j, khi đó quan hệ DP được xác định bởi -
dp1 [i] [j] =phút {dp1 [i - 1] [k]} + | j - A [i] |
với mọi k sao cho | k - j | ≤ mục tiêu
Trong trường hợp này, 0 ≤ i ≤ n và 0 ≤ j ≤ M trong đó n là số phần tử trong mảng và M =100. Vì vậy, tất cả k giá trị được xem xét theo cách này sao cho max (j - target, 0) ≤ k ≤ min (M, j + target) Cuối cùng, chi phí điều chỉnh tối thiểu của mảng sẽ là min {dp1 [n - 1] [j]} cho tất cả 0 ≤ j ≤ M.
Ví dụ
// 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;
} Đầu ra
Minimum adjustment cost is 35