C++에서 배열의 최소 조정 비용 찾기

컨셉

주어진 양의 정수 배열과 관련하여 배열의 각 요소를 교체하여 배열의 인접한 요소 간의 차이가 주어진 목표보다 작거나 같도록 합니다. 이제 조정 비용을 최소화하는 작업, 즉 새 값과 이전 값 간의 차이 합계입니다. 따라서 기본적으로 Σ|A[i] – A_new를 최소화해야 합니다. [나]| 여기서 0 ≤ i ≤ n-1, n은 A[] 및 A_new의 크기로 표시됩니다. []는 인접 차이가 target보다 작거나 같은 배열로 표시됩니다. 배열의 모든 요소를 ​​상수 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]|가능한 한 0에 가까워야 합니다. 또한,

|A[i] – A_신규 [i+1] ]| ≤ 목표.

여기서 이 문제는 DP(Dynamic Programming)로 해결할 수 있습니다.

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
//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