在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