แนวคิด
สำหรับอาร์เรย์ของจำนวนเต็มบวกที่กำหนด เราจะแทนที่แต่ละองค์ประกอบในอาร์เรย์เพื่อให้ความแตกต่างระหว่างองค์ประกอบที่อยู่ติดกันในอาร์เรย์มีค่าน้อยกว่าหรือเท่ากับเป้าหมายที่กำหนด ตอนนี้ งานของเราในการลดค่าใช้จ่ายในการปรับปรุง นั่นคือ ผลรวมของความแตกต่างระหว่างค่าใหม่และค่าเก่า ดังนั้น โดยพื้นฐานแล้วเราต้องย่อ Σ|A[i] – Aใหม่ [i]| โดยที่ 0 ≤ i ≤ n-1, n แสดงเป็นขนาดของ A[] และ Anew [] แสดงเป็นอาร์เรย์ที่มีความแตกต่างที่อยู่ติดกันน้อยกว่าหรือเท่ากับเป้าหมาย ให้องค์ประกอบทั้งหมดของอาร์เรย์มีขนาดเล็กกว่าค่าคงที่ M =100
อินพุต
arr = [56, 78, 53, 62, 40, 7, 26, 61, 50, 48], target = 20
ผลลัพธ์
Minimum adjustment cost is 35
วิธีการ
เพื่อลดต้นทุนการปรับ Σ|A[i] – Aใหม่ [i]| สำหรับดัชนี i ทั้งหมดในอาร์เรย์ เราจำได้ว่า |A[i] – Aใหม่ [i]|ควรใกล้เคียงกับศูนย์มากที่สุด ควรสังเกตด้วยว่า
|A[i] – Aใหม่ [i+1] ]| ≤ เป้าหมาย
ในที่นี้ ปัญหานี้สามารถแก้ไขได้ด้วยโปรแกรมไดนามิก (DP)
สมมติว่า dp1[i][j] แทนค่าปรับขั้นต่ำในการเปลี่ยน A[i] เป็น j จากนั้นความสัมพันธ์ DP จะถูกกำหนดโดย –
dp1[i][j] =นาที{dp1[i - 1][k]} + |j - A[i]|
สำหรับ k ทั้งหมดนั้น |k - j| ≤ เป้าหมาย
ในกรณีนี้ 0 ≤ i ≤ n และ 0 ≤ j ≤ M โดยที่ n คือจำนวนองค์ประกอบในอาร์เรย์และ M =100 ดังนั้น kvalues ทั้งหมดจึงถูกพิจารณาในลักษณะนี้ max(j – target, 0) ≤ k ≤ min(M, j + target) ในที่สุด ต้นทุนการปรับขั้นต่ำของอาร์เรย์จะเป็น min{dp1[n – 1][j]} สำหรับ 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
