在C ++中查找数组的最小调整成本
概念
对于给定的正整数数组，我们替换数组中的每个元素，以使数组中相邻元素之间的差小于或等于给定的目标。现在，我们的任务是最小化调整成本，即新值和旧值之间的差之和。因此，我们基本上需要最小化Σ|A[i]–一个新的[i]|其中0≤i≤n-1，n表示A[]的大小，而new[]表示相邻差小于或等于目标的数组。令数组的所有元素都小于常数M=100。
输入值
arr = [56, 78, 53, 62, 40, 7, 26, 61, 50, 48], target = 20
输出结果
Minimum adjustment cost is 35
方法
为了最小化调整成本Σ|A[i]–一个新的[i]|，对于数组中的所有索引i，我们都记得|A[i]–一个新的[i]|应该尽可能接近零。还应注意的是，
|A[i]–新的[i+1]]|≤目标。
在此，可以通过动态编程(DP)解决此问题。
假设dp1[i][j]表示将A[i]更改为j时的最小调整成本，则DP关系定义为–
dp1[i][j]=min{dp1[i-1][k]}+|j-A[i]|
对于所有k使得|k-j|≤目标
在这种情况下，0≤i≤n和0≤j≤M，其中n是数组中的元素数，M=100。因此，以这种方式考虑所有k值，使得max（j–target，0）≤k≤min（M，j+target）最后，对于所有0≤j≤M，数组的最小调整成本为min{dp1[n–1][j]}。
示例
// C++ program to find minimum adjustment cost of an array
#include <bits/stdc++.h>
using namespace std;
#define M1 100
//显示函数以查找数组的最小调整成本
int minAdjustmentCost(int A1[], int n1, int target1){
//dp1[i][j]存储更改时的最小调整成本
//A1[i]到j-
int dp1[n1][M1 + 1];
//分别处理数组的第一个元素
for (int j = 0; j <= M1; j++)
dp1[0][j] = abs(j - A1[0]);
//对数组的其余元素执行
for (int i = 1; i < n1; i++){
// Now replaceA1[i]到j- and calculate minimal adjustment
//成本dp1[i][j]
for (int j = 0; j <= M1; j++){
//我们将最小调整成本初始化为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));
}
}
//现在从dp表的最后一行返回最小值
int res1 = INT_MAX;
for (int j = 0; j <= M1; j++)
res1 = min(res1, dp1[n1 - 1][j]);
return res1;
}
//测试上述功能的驱动程序
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