logo

TechCodeview

Zoek de minimale aanpassingskosten van een array

Probeer het eens op GfG Practice ' title= #practiceLinkDiv {weergave: geen! belangrijk; }

Gegeven een array met positieve gehele getallen vervangt u elk element in de array zodanig dat het verschil tussen aangrenzende elementen in de array kleiner is dan of gelijk is aan een bepaald doel. We moeten de aanpassingskosten, die de som zijn van de verschillen tussen nieuwe en oude waarden, minimaliseren. Eigenlijk moeten we ?|A[i] - A minimaliserennieuw[ik]| waar 0? i ? n-1 n is de grootte van A[] en Anieuw[] is de array met een aangrenzend verschil kleiner dan of gelijk aan het doel. Neem aan dat alle elementen van de array kleiner zijn dan constant M = 100.

Voorbeelden:  



    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 Zoek de minimale aanpassingskosten van een array Probeer het!

Om de aanpassingskosten te minimaliseren ?|A[i] - Anieuw[ik]| voor alle index i in de array |A[i] - Anieuw[ik]| moet zo dicht mogelijk bij nul liggen. Ook |A[i] - Anieuw[i+1] ]| ? Doel.
Dit probleem kan worden opgelost door dynamische programmering .

int omzetten naar dubbele java

Stel dat dp[i][j] de minimale aanpassingskosten definieert bij het veranderen van A[i] in j, dan wordt de DP-relatie gedefinieerd door - 

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

Hier 0? i ? n en 0? J ? M waarbij n het aantal elementen in de array is en M = 100. We moeten alle k zo ​​beschouwen dat max(j - target 0) ? k? min(Mj + doel)
Ten slotte zullen de minimale aanpassingskosten van de array min{dp[n - 1][j]} zijn voor alle 0 ? J ? M.



Algoritme:

  • Creëer een 2D-array met de initialisaties dp[n][M+1] om de laagste aanpassingskosten vast te leggen van het veranderen van A[i] in j, waarbij n de lengte van de array is en M de maximale waarde ervan.
  • Bereken de kleinste aanpassingskosten voor het veranderen van A[0] in j voor het eerste element van de array dp[0][j] met behulp van de formule dp[0][j] = abs (j - A[0]).
  • Vervang A[i] door j in de resterende array-elementen dp[i][j] en gebruik de formule dp[i][j] = min(dp[i-1][k] + abs(A[i] - j)) waarbij k alle haalbare waarden tussen max(j-target0) en min(Mj+target) neemt om de minimale aanpassingskosten te krijgen.
  • Geef als minimale aanpassingskosten het laagste getal uit de laatste rij van de dp-tabel op. 

Hieronder ziet u de implementatie van het bovenstaande 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. ?>

Uitvoer 
Minimum adjustment cost is 75

Tijdcomplexiteit: O(n*m2)
Hulpruimte: O(n*m)




Efficiënte aanpak: Optimalisatie van de ruimte

In de vorige benadering de huidige waarde dp[i][j] is alleen afhankelijk van de huidige en vorige rijwaarden van DP . Om de complexiteit van de ruimte te optimaliseren, gebruiken we dus één enkele 1D-array om de berekeningen op te slaan.

maak de tekst vet in css

Implementatiestappen:

  • Maak een 1D-vector dp van grootte m+1 .
  • Stel een basisscenario in door de waarden van te initialiseren DP .
  • Herhaal nu de subproblemen met behulp van een geneste lus en haal de huidige waarde uit eerdere berekeningen.
  • Maak nu een tijdelijke 1d-vector vorige_dp gebruikt om de huidige waarden van eerdere berekeningen op te slaan.
  • Wijs na elke iteratie de waarde toe van vorige_dp naar dp voor verdere iteratie.
  • Initialiseer een variabele res om het definitieve antwoord op te slaan en bij te werken door de Dp te herhalen.
  • Eindelijk terug en print het definitieve antwoord dat is opgeslagen in res .

Uitvoering: 
 

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


Uitvoer 

Minimum adjustment cost is 75

Tijdcomplexiteit: O(n*m2)
Hulpruimte: O (m)

 

tekenreeksdatum converteren