KERESSE MEG EGY TÖMB MINIMÁLIS BEÁLLÍTÁSI KÖLTSÉGÉT

Próbáld ki a GfG Practice-n ' title=

#practiceLinkDiv { display: none !important; }

Adott egy pozitív egész tömb, cserélje ki a tömb minden elemét úgy, hogy a tömb szomszédos elemei közötti különbség kisebb vagy egyenlő legyen, mint egy adott cél. Minimalizálnunk kell a korrekciós költséget, amely az új és a régi értékek közötti különbségek összege. Alapvetően minimalizálnunk kell az ?|A[i] - A_új[i]| hol 0? i ? n-1 n A[] és A mérete_új[] az a tömb, amelynek szomszédos különbsége kisebb vagy egyenlő, mint a cél. Tegyük fel, hogy a tömb minden eleme kisebb, mint az M = 100 konstans.

Példák:

    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 Keresse meg egy tömb minimális beállítási költségét Próbáld ki!

tesztelés és a tesztelés típusai

Hagyja, hogy a dp[i][j] minimális korrekciós költséget definiáljon A[i] j-re történő megváltoztatásakor, akkor a DP relációt a -

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

Itt 0? én ? n és 0? j ? M ahol n a tömb elemeinek száma és M = 100. Minden k-t úgy kell tekintenünk, hogy max(j - target 0) ? k ? min (M j + cél)
Végül a tömb minimális beállítási költsége min{dp[n - 1][j]} lesz minden 0 ? j ? M.

Algoritmus:

Hozzon létre egy 2D tömböt a dp[n][M+1] inicializálással, hogy rögzítse az A[i] j-re történő módosításának legkisebb költségét, ahol n a tömb hossza és M a maximális értéke.
Számítsa ki a legkisebb korrekciós költséget, ha A[0]-t j-re változtatja a dp[0][j] tömb első elemére a dp[0][j] = abs (j - A[0]) képlet segítségével.
Cserélje ki az A[i]-t j-re a többi dp[i][j] tömbelemben, és használja a dp[i][j] = min(dp[i-1][k] + abs(A[i] - j)) képletet, ahol k minden lehetséges értéket felvesz max(j-cél0) és min(Mj+cél) között, hogy megkapja a minimális korrekciós költséget.
Minimális korrekciós költségként adja meg a legalacsonyabb számot a dp táblázat utolsó sorából.

Alább látható a fenti ötlet megvalósítása:

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. ?>

Kimenet

Minimum adjustment cost is 75

Időbeli összetettség: O(n*m²)
Kiegészítő tér: O(n *m)

Hatékony megközelítés: Tér optimalizálás

Az előző megközelítésben az aktuális érték dp[i][j] csak az aktuális és az előző sor értékétől függ DP . Tehát a tér összetettségének optimalizálása érdekében egyetlen 1D tömböt használunk a számítások tárolására.

A megvalósítás lépései:

valami gyors válogatás

Hozzon létre egy 1D vektort dp méretű m+1 .
Állítson be egy alapesetet az értékeinek inicializálásával DP .
Most ismételje meg a részproblémákat a beágyazott ciklus segítségével, és kapja meg az aktuális értéket a korábbi számításokból.
Most hozzon létre egy ideiglenes 1d vektort prev_dp a korábbi számításokból származó aktuális értékek tárolására szolgál.
Minden iteráció után rendelje hozzá az értékét prev_dp dp-re a további iterációhoz.
Változó inicializálása res a végső válasz tárolására és frissítésére a Dp-n keresztüli iterációval.
Végül térjen vissza, és nyomtassa ki a tárolt végső választ res .

Végrehajtás:

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

Kimenet

Minimum adjustment cost is 75

Időbeli összetettség: O(n*m²)
Kiegészítő tér: O (m)