Trova il costo minimo di aggiustamento di un array
#practiceLinkDiv { display: none! importante; } Dato un array di numeri interi positivi, sostituire ciascun elemento dell'array in modo tale che la differenza tra gli elementi adiacenti nell'array sia inferiore o uguale a un dato obiettivo. Dobbiamo ridurre al minimo il costo di aggiustamento che è la somma delle differenze tra valori nuovi e vecchi. Fondamentalmente dobbiamo minimizzare ?|A[i] - A nuovo [io]| dove 0? io ? n-1 n è la dimensione di A[] e A nuovo [] è l'array con differenza adiacente inferiore o uguale al target. Supponiamo che tutti gli elementi dell'array siano inferiori alla costante M = 100.
Esempi:
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 Trova il costo minimo di aggiustamento di un array Provalo!Per minimizzare il costo di aggiustamento ?|A[i] - A nuovo [io]| per tutto l'indice i nell'array |A[i] - A nuovo [io]| dovrebbe essere il più vicino possibile allo zero. Anche |A[i] - A nuovo [i+1] ]| ? Bersaglio.
Questo problema può essere risolto da programmazione dinamica .Supponiamo che dp[i][j] definisca il costo minimo di aggiustamento nel cambiare A[i] in j, quindi la relazione DP è definita da -
dp[i][j] = min{dp[i - 1][k]} + |j - A[i]|
for all k's such that |k - j| ? target
Qui 0? io ? n e 0? J ? M dove n è il numero di elementi nell'array e M = 100. Dobbiamo considerare tutti i k tali che max(j - target 0) ? k? min(M j + bersaglio)
Infine il costo minimo di aggiustamento dell'array sarà min{dp[n - 1][j]} per tutti gli 0 ? J ? M.Algoritmo:
- Creare un array 2D con le inizializzazioni dp[n][M+1] per registrare il costo di aggiustamento minimo derivante dalla modifica di A[i] in j dove n è la lunghezza dell'array e M è il suo valore massimo.
- Calcolare il costo di aggiustamento più piccolo derivante dalla modifica di A[0] in j per il primo elemento dell'array dp[0][j] utilizzando la formula dp[0][j] = abs (j - A[0]).
- Sostituisci A[i] con j negli elementi rimanenti dell'array dp[i][j] e utilizza la formula dp[i][j] = min(dp[i-1][k] + abs(A[i] - j)) dove k accetta tutti i valori possibili tra max(j-target0) e min(Mj+target) per ottenere il costo di aggiustamento minimo.
- Come costo di aggiustamento minimo, indicare il numero più basso dall'ultima riga della tabella dp.
Di seguito è riportata l'implementazione dell'idea di cui sopra:
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 - 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 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 - target 0 ); for ( ; k <= Math . min ( M j + 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 [ 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 ] = 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 [ 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 = int . MaxValue ; for ( int j = 0 ; j <= M ; j ++ ) res = Math . Min ( res dp [ n - 1 j ]); 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 - target 0 ); for ( ; k <= Math . min ( M j + 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. ?>
Produzione
Minimum adjustment cost is 75
Complessità temporale: O(n*m 2 )
Spazio ausiliario: O(n*m)
Approccio efficiente: Ottimizzazione dello spazio
Nell'approccio precedente il valore corrente dp[i][j] dipende solo dai valori della riga corrente e precedente di DP . Quindi, per ottimizzare la complessità dello spazio, utilizziamo un singolo array 1D per memorizzare i calcoli.
Fasi di implementazione:
- Crea un vettore 1D d.p di dimensione m+1 .
- Imposta un caso base inizializzando i valori di DP .
- Ora esegui l'iterazione sui sottoproblemi con l'aiuto del ciclo annidato e ottieni il valore corrente dai calcoli precedenti.
- Ora crea un vettore 1d temporaneo prev_dp utilizzato per memorizzare i valori correnti dei calcoli precedenti.
- Dopo ogni iterazione assegnare il valore di prev_dp a dp per ulteriori iterazioni.
- Inizializza una variabile ris per memorizzare la risposta finale e aggiornarla iterando attraverso il Dp.
- Alla fine ritorna e stampa la risposta finale memorizzata ris .
Attuazione:
#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
Produzione
Minimum adjustment cost is 75
Complessità temporale: O(n*m 2 )
Spazio ausiliario: O(m)
