C++でのアレイの最小調整コストを見つける

コンセプト

正の整数の特定の配列に関して、配列内の隣接する要素間の差が特定のターゲット以下になるように、配列内の各要素を置き換えます。次に、調整コストを最小化するタスク、つまり、新しい値と古い値の差の合計。したがって、基本的にΣ| A [i] – A _newを最小化する必要があります。 [i] |ここで、0≤i≤n-1、nはA[]およびA _newのサイズとして示されます。 []は、隣接する差がターゲット以下の配列として示されます。配列のすべての要素が定数M=100よりも小さいとします。

入力

arr = [56, 78, 53, 62, 40, 7, 26, 61, 50, 48], target = 20

出力

Minimum adjustment cost is 35

メソッド

調整コストを最小限に抑えるためにΣ|A[i] – A _new [i] |、配列内のすべてのインデックスiについて、| A [i] – A _new [i]|可能な限りゼロに近づける必要があります。また、

| A [i] –A_新しい [i + 1]] | ≤ターゲット。

ここで、この問題は動的計画法（DP）によって解決できます。

dp1 [i][j]がA[i]をjに変更する際の最小調整コストを表すと仮定すると、DP関係は–

dp1 [i] [j] =min {dp1 [i-1] [k]} + | j-A [i] |

| k--j|のようなすべてのkに対して≤ターゲット

この場合、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
//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