POIŠČITE NAJMANJŠO PRILAGODITVENO CENO NIZA

Preizkusite na GfG Practice ' title=

#practiceLinkDiv { display: none !important; }

Podana matrika pozitivnih celih števil zamenja vsak element v matriki tako, da je razlika med sosednjimi elementi v matriki manjša ali enaka danemu cilju. Minimizirati moramo prilagoditvene stroške, ki so vsota razlik med novimi in starimi vrednostmi. V bistvu moramo minimizirati ?|A[i] - A_novo[i]| kje 0? jaz? n-1 n je velikost A[] in A_novo[] je niz s sosednjo razliko, ki je manjša ali enaka cilju. Predpostavimo, da so vsi elementi matrike manjši od konstante M = 100.

Primeri:

    Input:    arr = [1 3 0 3] target = 1  
    Output:    Minimum adjustment cost is 3  
    Explanation:    One of the possible solutions   
is [2 3 2 3]  
    Input:    arr = [2 3 2 3] target = 1  
    Output:    Minimum adjustment cost is 0  
    Explanation:     All adjacent elements in the input   
array are already less than equal to given target  
    Input:    arr = [55 77 52 61 39 6   
 25 60 49 47] target = 10  
    Output:    Minimum adjustment cost is 75  
    Explanation:    One of the possible solutions is   
[55 62 52 49 39 29 30 40 49 47]

Recommended Practice Poiščite najmanjšo prilagoditveno ceno niza Poskusite!

Naj dp[i][j] določa minimalne prilagoditvene stroške pri spremembi A[i] v j, potem je razmerje DP definirano z -

dp[i][j] = min{dp[i - 1][k]} + |j - A[i]|  
 for all k's such that |k - j| ? target

Tukaj 0? jaz? n in 0? j? M, kjer je n število elementov v nizu in M = 100. Upoštevati moramo vse k, tako da max(j - cilj 0)? k? min (M j + cilj)
Končno bo minimalni prilagoditveni strošek matrike min{dp[n - 1][j]} za vse 0 ? j? M.

Algoritem:

Ustvarite 2D matriko z inicializacijami dp[n][M+1], da zabeležite najmanjše prilagoditvene stroške spreminjanja A[i] v j, kjer je n dolžina matrike in M njena največja vrednost.
Izračunajte najmanjši prilagoditveni strošek spremembe A[0] v j za prvi element matrike dp[0][j] z uporabo formule dp[0][j] = abs (j - A[0]).
Zamenjajte A[i] z j v preostalih elementih polja dp[i][j] in uporabite formulo dp[i][j] = min(dp[i-1][k] + abs(A[i] - j)), kjer k zavzame vse možne vrednosti med max(j-target0) in min(Mj+target), da dobite minimalne stroške prilagoditve.
Kot najmanjši strošek prilagoditve navedite najnižjo številko iz zadnje vrstice tabele dp.

Spodaj je izvedba zgornje ideje:

C++

// C++ program to find minimum adjustment cost of an array #include    using namespace std; #define M 100 // Function to find minimum adjustment cost of an array int minAdjustmentCost(int A[] int n int target) {  // dp[i][j] stores minimal adjustment cost on changing  // A[i] to j  int dp[n][M + 1];  // handle first element of array separately  for (int j = 0; j <= M; j++)  dp[0][j] = abs(j - A[0]);  // do for rest elements of the array  for (int i = 1; i < n; i++)  {  // replace A[i] to j and calculate minimal adjustment  // cost dp[i][j]  for (int j = 0; j <= M; j++)  {  // initialize minimal adjustment cost to INT_MAX  dp[i][j] = INT_MAX;  // consider all k such that k >= max(j - target 0) and  // k <= min(M j + target) and take minimum  for (int k = max(j-target0); k <= min(Mj+target); k++)  dp[i][j] = min(dp[i][j] dp[i - 1][k] + abs(A[i] - j));  }  }   // return minimum value from last row of dp table  int res = INT_MAX;   for (int j = 0; j <= M; j++)  res = min(res dp[n - 1][j]);  return res; } // Driver Program to test above functions int main() {  int arr[] = {55 77 52 61 39 6 25 60 49 47};  int n = sizeof(arr) / sizeof(arr[0]);  int target = 10;  cout << 'Minimum adjustment cost is '  << minAdjustmentCost(arr n target) << endl;  return 0; }

Java

// Java program to find minimum adjustment cost of an array import java.io.*; import java.util.*; class GFG  {  public static int M = 100;    // Function to find minimum adjustment cost of an array  static int minAdjustmentCost(int A[] int n int target)  {  // dp[i][j] stores minimal adjustment cost on changing  // A[i] to j  int[][] dp = new int[n][M + 1];    // handle first element of array separately  for (int j = 0; j <= M; j++)  dp[0][j] = Math.abs(j - A[0]);    // do for rest elements of the array  for (int i = 1; i < n; i++)  {  // replace A[i] to j and calculate minimal adjustment  // cost dp[i][j]  for (int j = 0; j <= M; j++)  {  // initialize minimal adjustment cost to INT_MAX  dp[i][j] = Integer.MAX_VALUE;    // consider all k such that k >= max(j - target 0) and  // k <= min(M j + target) and take minimum  int k = Math.max(j-target0);  for ( ; k <= Math.min(Mj+target); k++)  dp[i][j] = Math.min(dp[i][j] dp[i - 1][k] +   Math.abs(A[i] - j));  }  }     // return minimum value from last row of dp table  int res = Integer.MAX_VALUE;   for (int j = 0; j <= M; j++)  res = Math.min(res dp[n - 1][j]);    return res;  }    // Driver program  public static void main (String[] args)   {  int arr[] = {55 77 52 61 39 6 25 60 49 47};  int n = arr.length;  int target = 10;    System.out.println('Minimum adjustment cost is '  +minAdjustmentCost(arr n target));  } } // This code is contributed by Pramod Kumar

Python3

# Python3 program to find minimum # adjustment cost of an array  M = 100 # Function to find minimum # adjustment cost of an array def minAdjustmentCost(A n target): # dp[i][j] stores minimal adjustment  # cost on changing A[i] to j  dp = [[0 for i in range(M + 1)] for i in range(n)] # handle first element # of array separately for j in range(M + 1): dp[0][j] = abs(j - A[0]) # do for rest elements  # of the array  for i in range(1 n): # replace A[i] to j and  # calculate minimal adjustment # cost dp[i][j]  for j in range(M + 1): # initialize minimal adjustment # cost to INT_MAX dp[i][j] = 100000000 # consider all k such that # k >= max(j - target 0) and # k <= min(M j + target) and  # take minimum for k in range(max(j - target 0) min(M j + target) + 1): dp[i][j] = min(dp[i][j] dp[i - 1][k] + abs(A[i] - j)) # return minimum value from  # last row of dp table res = 10000000 for j in range(M + 1): res = min(res dp[n - 1][j]) return res # Driver Code  arr= [55 77 52 61 39 6 25 60 49 47] n = len(arr) target = 10 print('Minimum adjustment cost is' minAdjustmentCost(arr n target) sep = ' ') # This code is contributed  # by sahilshelangia

// C# program to find minimum adjustment // cost of an array using System; class GFG {    public static int M = 100;    // Function to find minimum adjustment  // cost of an array  static int minAdjustmentCost(int []A int n  int target)  {    // dp[i][j] stores minimal adjustment  // cost on changing A[i] to j  int[] dp = new int[nM + 1];  // handle first element of array  // separately  for (int j = 0; j <= M; j++)  dp[0j] = Math.Abs(j - A[0]);  // do for rest elements of the array  for (int i = 1; i < n; i++)  {  // replace A[i] to j and calculate  // minimal adjustment cost dp[i][j]  for (int j = 0; j <= M; j++)  {  // initialize minimal adjustment  // cost to INT_MAX  dp[ij] = int.MaxValue;  // consider all k such that   // k >= max(j - target 0) and  // k <= min(M j + target) and  // take minimum  int k = Math.Max(j - target 0);    for ( ; k <= Math.Min(M j +  target); k++)  dp[ij] = Math.Min(dp[ij]  dp[i - 1k]  + Math.Abs(A[i] - j));  }  }   // return minimum value from last  // row of dp table  int res = int.MaxValue;   for (int j = 0; j <= M; j++)  res = Math.Min(res dp[n - 1j]);  return res;  }    // Driver program  public static void Main ()   {  int []arr = {55 77 52 61 39  6 25 60 49 47};  int n = arr.Length;  int target = 10;  Console.WriteLine('Minimum adjustment'  + ' cost is '  + minAdjustmentCost(arr n target));  } } // This code is contributed by Sam007.

JavaScript

<script>  // Javascript program to find minimum adjustment cost of an array  let M = 100;    // Function to find minimum adjustment cost of an array  function minAdjustmentCost(A n target)  {    // dp[i][j] stores minimal adjustment cost on changing  // A[i] to j  let dp = new Array(n);  for (let i = 0; i < n; i++)  {  dp[i] = new Array(n);  for (let j = 0; j <= M; j++)  {  dp[i][j] = 0;  }  }    // handle first element of array separately  for (let j = 0; j <= M; j++)  dp[0][j] = Math.abs(j - A[0]);    // do for rest elements of the array  for (let i = 1; i < n; i++)  {  // replace A[i] to j and calculate minimal adjustment  // cost dp[i][j]  for (let j = 0; j <= M; j++)  {  // initialize minimal adjustment cost to INT_MAX  dp[i][j] = Number.MAX_VALUE;    // consider all k such that k >= max(j - target 0) and  // k <= min(M j + target) and take minimum  let k = Math.max(j-target0);  for ( ; k <= Math.min(Mj+target); k++)  dp[i][j] = Math.min(dp[i][j] dp[i - 1][k] +   Math.abs(A[i] - j));  }  }     // return minimum value from last row of dp table  let res = Number.MAX_VALUE;   for (let j = 0; j <= M; j++)  res = Math.min(res dp[n - 1][j]);    return res;  }    let arr = [55 77 52 61 39 6 25 60 49 47];  let n = arr.length;  let target = 10;  document.write('Minimum adjustment cost is '  +minAdjustmentCost(arr n target));    // This code is contributed by decode2207. </script>

PHP

 // PHP program to find minimum  // adjustment cost of an array $M = 100; // Function to find minimum  // adjustment cost of an array function minAdjustmentCost( $A $n $target) { // dp[i][j] stores minimal  // adjustment cost on changing // A[i] to j global $M; $dp = array(array()); // handle first element  // of array separately for($j = 0; $j <= $M; $j++) $dp[0][$j] = abs($j - $A[0]); // do for rest  // elements of the array for($i = 1; $i < $n; $i++) { // replace A[i] to j and  // calculate minimal adjustment // cost dp[i][j] for($j = 0; $j <= $M; $j++) { // initialize minimal adjustment // cost to INT_MAX $dp[$i][$j] = PHP_INT_MAX; // consider all k such that  // k >= max(j - target 0) and // k <= min(M j + target) and // take minimum for($k = max($j - $target 0); $k <= min($M $j + $target); $k++) $dp[$i][$j] = min($dp[$i][$j] $dp[$i - 1][$k] + abs($A[$i] - $j)); } } // return minimum value  // from last row of dp table $res = PHP_INT_MAX; for($j = 0; $j <= $M; $j++) $res = min($res $dp[$n - 1][$j]); return $res; } // Driver Code $arr = array(55 77 52 61 39 6 25 60 49 47); $n = count($arr); $target = 10; echo 'Minimum adjustment cost is '  minAdjustmentCost($arr $n $target); // This code is contributed by anuj_67. ?>

Izhod

Minimum adjustment cost is 75

Časovna zapletenost: O(n*m²)
Pomožni prostor: O(n *m)

Učinkovit pristop: Optimizacija prostora

Pri prejšnjem pristopu trenutna vrednost dp[i][j] je odvisno le od trenutne in prejšnje vrednosti vrstice DP . Za optimizacijo kompleksnosti prostora uporabljamo eno samo 1D polje za shranjevanje izračunov.

Izvedbeni koraki:

Ustvarite 1D vektor dp velikosti m+1 .
Nastavite osnovni primer z inicializacijo vrednosti DP .
Zdaj ponovite podprobleme s pomočjo ugnezdene zanke in pridobite trenutno vrednost iz prejšnjih izračunov.
Zdaj ustvarite začasni 1d vektor prev_dp uporablja se za shranjevanje trenutnih vrednosti iz prejšnjih izračunov.
Po vsaki ponovitvi dodelite vrednost prev_dp na dp za nadaljnjo ponovitev.
Inicializirajte spremenljivko res da shranite končni odgovor in ga posodobite s ponavljanjem skozi Dp.
Nazadnje se vrnite in natisnite končni odgovor, shranjen v res .

Izvedba:

C++

#include    using namespace std; #define M 100 // Function to find minimum adjustment cost of an array int minAdjustmentCost(int A[] int n int target) {  int dp[M + 1]; // Array to store the minimum adjustment costs for each value  for (int j = 0; j <= M; j++)  dp[j] = abs(j - A[0]); // Initialize the first row with the absolute differences  for (int i = 1; i < n; i++) // Iterate over the array elements  {  int prev_dp[M + 1];  memcpy(prev_dp dp sizeof(dp)); // Store the previous row's minimum costs  for (int j = 0; j <= M; j++) // Iterate over the possible values  {  dp[j] = INT_MAX; // Initialize the current value with maximum cost  // Find the minimum cost by considering the range of previous values  for (int k = max(j - target 0); k <= min(M j + target); k++)  dp[j] = min(dp[j] prev_dp[k] + abs(A[i] - j));  }  }  int res = INT_MAX;  for (int j = 0; j <= M; j++)  res = min(res dp[j]); // Find the minimum cost in the last row  return res; // Return the minimum adjustment cost } int main() {  int arr[] = {55 77 52 61 39 6 25 60 49 47};  int n = sizeof(arr) / sizeof(arr[0]);  int target = 10;  cout << 'Minimum adjustment cost is '  << minAdjustmentCost(arr n target) << endl;  return 0; }

Java

import java.util.Arrays; public class MinimumAdjustmentCost {  static final int M = 100;  // Function to find the minimum adjustment cost of an array  static int minAdjustmentCost(int[] A int n int target) {  int[] dp = new int[M + 1];  // Initialize the first row with absolute differences  for (int j = 0; j <= M; j++) {  dp[j] = Math.abs(j - A[0]);  }  // Iterate over the array elements  for (int i = 1; i < n; i++) {  int[] prev_dp = Arrays.copyOf(dp dp.length); // Store the previous row's minimum costs  // Iterate over the possible values  for (int j = 0; j <= M; j++) {  dp[j] = Integer.MAX_VALUE; // Initialize the current value with maximum cost  // Find the minimum cost by considering the range of previous values  for (int k = Math.max(j - target 0); k <= Math.min(M j + target); k++) {  dp[j] = Math.min(dp[j] prev_dp[k] + Math.abs(A[i] - j));  }  }  }  int res = Integer.MAX_VALUE;  for (int j = 0; j <= M; j++) {  res = Math.min(res dp[j]); // Find the minimum cost in the last row  }  return res; // Return the minimum adjustment cost  }  public static void main(String[] args) {  int[] arr = { 55 77 52 61 39 6 25 60 49 47 };  int n = arr.length;  int target = 10;  System.out.println('Minimum adjustment cost is ' + minAdjustmentCost(arr n target));  } }

Python3

def min_adjustment_cost(A n target): M = 100 dp = [0] * (M + 1) # Initialize the first row of dp with absolute differences for j in range(M + 1): dp[j] = abs(j - A[0]) # Iterate over the array elements for i in range(1 n): prev_dp = dp[:] # Store the previous row's minimum costs for j in range(M + 1): dp[j] = float('inf') # Initialize the current value with maximum cost # Find the minimum cost by considering the range of previous values for k in range(max(j - target 0) min(M j + target) + 1): dp[j] = min(dp[j] prev_dp[k] + abs(A[i] - j)) res = float('inf') for j in range(M + 1): res = min(res dp[j]) # Find the minimum cost in the last row return res if __name__ == '__main__': arr = [55 77 52 61 39 6 25 60 49 47] n = len(arr) target = 10 print('Minimum adjustment cost is' min_adjustment_cost(arr n target))

using System; class Program {  const int M = 100;  // Function to find minimum adjustment cost of an array  static int MinAdjustmentCost(int[] A int n int target)  {  int[] dp = new int[M + 1]; // Array to store the minimum adjustment costs for each value  for (int j = 0; j <= M; j++)  {  dp[j] = Math.Abs(j - A[0]); // Initialize the first row with the absolute differences  }  for (int i = 1; i < n; i++) // Iterate over the array elements  {  int[] prevDp = (int[])dp.Clone(); // Store the previous row's minimum costs  for (int j = 0; j <= M; j++) // Iterate over the possible values  {  dp[j] = int.MaxValue; // Initialize the current value with maximum cost  // Find the minimum cost by considering the range of previous values  for (int k = Math.Max(j - target 0); k <= Math.Min(M j + target); k++)  {  dp[j] = Math.Min(dp[j] prevDp[k] + Math.Abs(A[i] - j));  }  }  }  int res = int.MaxValue;  for (int j = 0; j <= M; j++)  {  res = Math.Min(res dp[j]); // Find the minimum cost in the last row  }  return res; // Return the minimum adjustment cost  }  static void Main()  {  int[] arr = { 55 77 52 61 39 6 25 60 49 47 };  int n = arr.Length;  int target = 10;  Console.WriteLine('Minimum adjustment cost is ' + MinAdjustmentCost(arr n target));  } }

JavaScript

const M = 100; // Function to find minimum adjustment cost of an array function minAdjustmentCost(A n target) {  let dp = new Array(M + 1); // Array to store the minimum adjustment costs for each value  for (let j = 0; j <= M; j++)  dp[j] = Math.abs(j - A[0]); // Initialize the first row with the absolute differences  for (let i = 1; i < n; i++) // Iterate over the array elements  {  let prev_dp = [...dp]; // Store the previous row's minimum costs  for (let j = 0; j <= M; j++) // Iterate over the possible values  {  dp[j] = Number.MAX_VALUE; // Initialize the current value with maximum cost  // Find the minimum cost by considering the range of previous values  for (let k = Math.max(j - target 0); k <= Math.min(M j + target); k++)  dp[j] = Math.min(dp[j] prev_dp[k] + Math.abs(A[i] - j));  }  }  let res = Number.MAX_VALUE;  for (let j = 0; j <= M; j++)  res = Math.min(res dp[j]); // Find the minimum cost in the last row  return res; // Return the minimum adjustment cost } let arr = [55 77 52 61 39 6 25 60 49 47]; let n = arr.length; let target = 10; console.log('Minimum adjustment cost is ' + minAdjustmentCost(arr n target)); // This code is contributed by Kanchan Agarwal

Izhod

Minimum adjustment cost is 75

Časovna zapletenost: O(n*m²)
Pomožni prostor: O (m)