logo

TechCodeview

Finden Sie die minimalen Anpassungskosten eines Arrays

Probieren Sie es bei GfG Practice aus ' title= #practiceLinkDiv { display: none !important; }

Ersetzen Sie bei einem gegebenen Array positiver Ganzzahlen jedes Element im Array so, dass die Differenz zwischen benachbarten Elementen im Array kleiner oder gleich einem bestimmten Ziel ist. Wir müssen die Anpassungskosten minimieren, die sich aus der Summe der Unterschiede zwischen neuen und alten Werten ergeben. Wir müssen grundsätzlich ?|A[i] - A minimierenneu[i]| wo 0 ? ich ? n-1 n ist die Größe von A[] und Aneu[] ist das Array mit benachbarten Differenzen, die kleiner oder gleich dem Ziel sind. Angenommen, alle Elemente des Arrays sind kleiner als die Konstante M = 100.

Beispiele:  



    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 Finden Sie die minimalen Anpassungskosten eines Arrays Probieren Sie es aus!

Um den Anpassungsaufwand zu minimieren ?|A[i] - Aneu[i]| für alle Indexe i im Array |A[i] - Aneu[i]| sollte so nahe wie möglich bei Null liegen. Auch |A[i] - Aneu[i+1] ]| ? Ziel.
Dieses Problem kann gelöst werden durch dynamische Programmierung .

Wenn dp[i][j] den minimalen Anpassungsaufwand bei der Änderung von A[i] in j definiert, dann ist die DP-Beziehung definiert durch – 

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

Hier 0 ? ich ? n und 0 ? J ? M, wobei n die Anzahl der Elemente im Array und M = 100 ist. Wir müssen alle k berücksichtigen, sodass max(j - Ziel 0) ? k ? min(M j + Ziel)
Schließlich beträgt der minimale Anpassungsaufwand des Arrays min{dp[n - 1][j]} für alle 0 ? J ? M.



Algorithmus:

  • Erstellen Sie ein 2D-Array mit den Initialisierungen dp[n][M+1], um den geringsten Anpassungsaufwand für die Änderung von A[i] in j aufzuzeichnen, wobei n die Länge des Arrays und M sein Maximalwert ist.
  • Berechnen Sie den kleinsten Anpassungsaufwand für die Änderung von A[0] in j für das erste Element des Arrays dp[0][j] mithilfe der Formel dp[0][j] = abs (j – A[0]).
  • Ersetzen Sie A[i] durch j in den verbleibenden Array-Elementen dp[i][j] und verwenden Sie die Formel dp[i][j] = min(dp[i-1][k] + abs(A[i] - j)), wobei k alle möglichen Werte zwischen max(j-target0) und min(Mj+target) annimmt, um die minimalen Anpassungskosten zu erhalten.
  • Geben Sie als minimalen Anpassungsaufwand die niedrigste Zahl aus der letzten Zeile der dp-Tabelle an. 

Nachfolgend finden Sie die Umsetzung der obigen Idee:

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

Ausgabe 
Minimum adjustment cost is 75

Zeitkomplexität: O(n*m2)
Hilfsraum: O(n *m)




Effizienter Ansatz: Platzoptimierung

Im vorherigen Ansatz der aktuelle Wert dp[i][j] hängt nur von den aktuellen und vorherigen Zeilenwerten ab DP . Um die räumliche Komplexität zu optimieren, verwenden wir ein einzelnes 1D-Array zum Speichern der Berechnungen.

Umsetzungsschritte:

  • Erstellen Sie einen 1D-Vektor dp der Größe m+1 .
  • Legen Sie einen Basisfall fest, indem Sie die Werte von initialisieren DP .
  • Nun iterieren Sie mit Hilfe einer verschachtelten Schleife über Teilprobleme und erhalten Sie den aktuellen Wert aus vorherigen Berechnungen.
  • Erstellen Sie nun einen temporären 1D-Vektor prev_dp Wird verwendet, um die aktuellen Werte aus früheren Berechnungen zu speichern.
  • Weisen Sie nach jeder Iteration den Wert von zu prev_dp zu dp für die weitere Iteration.
  • Initialisieren Sie eine Variable res um die endgültige Antwort zu speichern und durch Iteration durch den Dp zu aktualisieren.
  • Kehren Sie schließlich zurück und drucken Sie die endgültige Antwort aus, die in gespeichert ist res .

Durchführung: 
 

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))
C# 
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


Ausgabe

Javafx-Tutorial 
Minimum adjustment cost is 75

Zeitkomplexität: O(n*m2)
Hilfsraum: O (m)