logo

TechCodeview

Znajdź minimalny koszt dostosowania tablicy

Wypróbuj w praktyce GfG ' title= #practiceLinkDiv { display: none !important; }

Biorąc pod uwagę tablicę dodatnich liczb całkowitych, zamień każdy element w tablicy w taki sposób, aby różnica między sąsiednimi elementami w tablicy była mniejsza lub równa danej wartości docelowej. Musimy zminimalizować koszt dostosowania, czyli sumę różnic pomiędzy nowymi i starymi wartościami. Zasadniczo musimy zminimalizować ?|A[i] - Anowy[ja]| gdzie 0? I ? n-1 n to rozmiar A[] i Anowy[] to tablica z różnicą sąsiednich mniejszą lub równą wartości docelowej. Załóżmy, że wszystkie elementy tablicy są mniejsze od stałej M = 100.

Przykłady:  



    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 Znajdź minimalny koszt dostosowania tablicy Spróbuj!

Aby zminimalizować koszt dostosowania ?|A[i] - Anowy[ja]| dla wszystkich indeksów i w tablicy |A[i] - Anowy[ja]| powinien być jak najbliżej zera. Również |A[i] - Anowy[i+1] ]| ? Cel.
Problem ten można rozwiązać poprzez programowanie dynamiczne .

przekonwertuj na ciąg Java

Niech dp[i][j] definiuje minimalny koszt dostosowania przy zmianie A[i] na j, wówczas relację DP definiujemy wzorem - 

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

Tutaj 0? I ? n i 0? J ? M gdzie n jest liczbą elementów w tablicy, a M = 100. Musimy rozważyć wszystkie k w taki sposób, że max(j - cel 0) ? k? min(Mj + cel)
Ostatecznie minimalny koszt dostosowania tablicy wyniesie min{dp[n - 1][j]} dla wszystkich 0? J ? M.



Algorytm:

  • Utwórz tablicę 2D z inicjacjami dp[n][M+1], aby zapisać najmniejszy koszt dostosowania zmiany A[i] na j, gdzie n to długość tablicy, a M to jej maksymalna wartość.
  • Oblicz najmniejszy koszt dostosowania zmiany A[0] na j dla pierwszego elementu tablicy dp[0][j] korzystając ze wzoru dp[0][j] = abs (j - A[0]).
  • Zamień A[i] na j w pozostałych elementach tablicy dp[i][j] i użyj wzoru dp[i][j] = min(dp[i-1][k] + abs(A[i] - j)) gdzie k przyjmuje wszystkie możliwe wartości z zakresu max(j-target0) do min(Mj+target), aby uzyskać minimalny koszt dostosowania.
  • Jako minimalny koszt dostosowania należy podać najniższą liczbę z ostatniego wiersza tabeli dp. 

Poniżej realizacja powyższego pomysłu:

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

Wyjście 
Minimum adjustment cost is 75

Złożoność czasowa: O(n*m2)
Przestrzeń pomocnicza: O(n*m)




Skuteczne podejście: Optymalizacja przestrzeni

c# data i godzina

W poprzednim podejściu bieżąca wartość dp[i]j] zależy tylko od wartości bieżącego i poprzedniego wiersza DP . Aby zoptymalizować złożoność przestrzeni, używamy pojedynczej tablicy 1D do przechowywania obliczeń.

Etapy wdrożenia:

przykłady dfa
  • Utwórz wektor 1D dp wielkościowy m+1 .
  • Ustaw przypadek podstawowy, inicjując wartości DP .
  • Teraz wykonaj iterację po podproblemach za pomocą zagnieżdżonej pętli i uzyskaj bieżącą wartość z poprzednich obliczeń.
  • Teraz utwórz tymczasowy wektor 1d poprzedni_dp używany do przechowywania bieżących wartości z poprzednich obliczeń.
  • Po każdej iteracji przypisz wartość poprzedni_dp do dp w celu dalszej iteracji.
  • Zainicjuj zmienną rez aby zapisać ostateczną odpowiedź i zaktualizować ją, iterując po Dp.
  • Na koniec wróć i wydrukuj ostateczną odpowiedź zapisaną w rez .

Realizacja: 
 

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


Wyjście 

Minimum adjustment cost is 75

Złożoność czasowa: O(n*m2)
Przestrzeń pomocnicza: O (m)