Găsiți costul minim de ajustare al unei matrice
Încercați-l pe GfG Practice 
#practiceLinkDiv { display: none !important; }
Ieșire
#practiceLinkDiv { display: none !important; } Având în vedere o matrice de numere întregi pozitive, înlocuiți fiecare element din matrice astfel încât diferența dintre elementele adiacente din matrice să fie mai mică sau egală cu o țintă dată. Trebuie să minimizăm costul de ajustare care este suma diferențelor dintre valorile noi și cele vechi. Practic, trebuie să minimizăm ?|A[i] - A nou [i]| unde 0? eu? n-1 n este dimensiunea lui A[] și A nou [] este matricea cu diferența adiacentă mai mică sau egală cu ținta. Să presupunem că toate elementele matricei sunt mai mici decât constanta M = 100.
Exemple:
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 Găsiți costul minim de ajustare al unei matrice Încearcă!Pentru a minimiza costul de ajustare ?|A[i] - A nou [i]| pentru tot indexul i din tabloul |A[i] - A nou [i]| ar trebui să fie cât mai aproape de zero. De asemenea |A[i] - A nou [i+1] ]| ? Ţintă.
Această problemă poate fi rezolvată prin programare dinamică .Fie dp[i][j] definește costul minim de ajustare la schimbarea A[i] la j, atunci relația DP este definită de -
dp[i][j] = min{dp[i - 1][k]} + |j - A[i]|
for all k's such that |k - j| ? target
Aici 0? eu? n si 0 ? j ? M unde n este numărul de elemente din tablou și M = 100. Trebuie să luăm în considerare toate k astfel încât max(j - target 0) ? k ? min(M j + țintă)
În cele din urmă, costul minim de ajustare al matricei va fi min{dp[n - 1][j]} pentru toate 0 ? j ? M.Algoritm:
- Creați o matrice 2D cu inițializările dp[n][M+1] pentru a înregistra cel mai mic cost de ajustare al schimbării A[i] la j unde n este lungimea matricei și M este valoarea sa maximă.
- Calculați cel mai mic cost de ajustare al schimbării A[0] în j pentru primul element al matricei dp[0][j] folosind formula dp[0][j] = abs (j - A[0]).
- Înlocuiți A[i] cu j în elementele de matrice rămase dp[i][j] și utilizați formula dp[i][j] = min(dp[i-1][k] + abs(A[i] - j)) unde k ia toate valorile fezabile între max(j-target0) și min(Mj+target) pentru a obține costul minim de ajustare.
- Ca cost minim de ajustare, dați cel mai mic număr din ultimul rând al tabelului dp.
Mai jos este implementarea ideii de mai sus:
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. ?>
Ieșire
Minimum adjustment cost is 75
Complexitatea timpului: O(n*m 2 )
Spațiu auxiliar: O(n *m)
Abordare eficientă: Optimizarea spațiului
În abordarea anterioară valoarea curentă dp[i][j] depinde numai de valorile rândurilor curente și anterioare ale DP . Deci, pentru a optimiza complexitatea spațiului, folosim o singură matrice 1D pentru a stoca calculele.
Etape de implementare:
- Creați un vector 1D dp de mărime m+1 .
- Setați un caz de bază prin inițializarea valorilor lui DP .
- Acum repetați peste subprobleme cu ajutorul buclei imbricate și obțineți valoarea curentă din calculele anterioare.
- Acum creați un vector 1d temporar prev_dp folosit pentru a stoca valorile curente din calculele anterioare.
- După fiecare iterație atribuiți valoarea lui prev_dp la dp pentru o iterație ulterioară.
- Inițializați o variabilă res pentru a stoca răspunsul final și a-l actualiza prin iterare prin Dp.
- La sfârșit, întoarceți și imprimați răspunsul final stocat în res .
Implementare:
#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
Ieșire
Minimum adjustment cost is 75
Complexitatea timpului: O(n*m 2 )
Spațiu auxiliar: O (m)
