Keresse meg egy tömb minimális beállítási költségét
Próbáld ki a GfG Practice-n 
#practiceLinkDiv { display: none !important; }
Kimenet
#practiceLinkDiv { display: none !important; } Adott egy pozitív egész tömb, cserélje ki a tömb minden elemét úgy, hogy a tömb szomszédos elemei közötti különbség kisebb vagy egyenlő legyen, mint egy adott cél. Minimalizálnunk kell a korrekciós költséget, amely az új és a régi értékek közötti különbségek összege. Alapvetően minimalizálnunk kell az ?|A[i] - A új [i]| hol 0? i ? n-1 n A[] és A mérete új [] az a tömb, amelynek szomszédos különbsége kisebb vagy egyenlő, mint a cél. Tegyük fel, hogy a tömb minden eleme kisebb, mint az M = 100 konstans.
Példák:
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 Keresse meg egy tömb minimális beállítási költségét Próbáld ki!A beállítási költség minimalizálása érdekében ?|A[i] - A új [i]| a tömb összes i indexére |A[i] - A új [i]| a lehető legközelebb kell lennie a nullához. Szintén |A[i] - A új [i+1] ]| ? Cél.
Ezt a problémát úgy lehet megoldani dinamikus programozás .Hagyja, hogy a dp[i][j] minimális korrekciós költséget definiáljon A[i] j-re történő megváltoztatásakor, akkor a DP relációt a -
dp[i][j] = min{dp[i - 1][k]} + |j - A[i]|
for all k's such that |k - j| ? target
Itt 0? én ? n és 0? j ? M ahol n a tömb elemeinek száma és M = 100. Minden k-t úgy kell tekintenünk, hogy max(j - target 0) ? k ? min (M j + cél)
Végül a tömb minimális beállítási költsége min{dp[n - 1][j]} lesz minden 0 ? j ? M.Algoritmus:
- Hozzon létre egy 2D tömböt a dp[n][M+1] inicializálással, hogy rögzítse az A[i] j-re történő módosításának legkisebb költségét, ahol n a tömb hossza és M a maximális értéke.
- Számítsa ki a legkisebb korrekciós költséget, ha A[0]-t j-re változtatja a dp[0][j] tömb első elemére a dp[0][j] = abs (j - A[0]) képlet segítségével.
- Cserélje ki az A[i]-t j-re a többi dp[i][j] tömbelemben, és használja a dp[i][j] = min(dp[i-1][k] + abs(A[i] - j)) képletet, ahol k minden lehetséges értéket felvesz max(j-cél0) és min(Mj+cél) között, hogy megkapja a minimális korrekciós költséget.
- Minimális korrekciós költségként adja meg a legalacsonyabb számot a dp táblázat utolsó sorából.
Alább látható a fenti ötlet megvalósítása:
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. ?>
Kimenet
Minimum adjustment cost is 75
Időbeli összetettség: O(n*m 2 )
Kiegészítő tér: O(n *m)
Hatékony megközelítés: Tér optimalizálás
Az előző megközelítésben az aktuális érték dp[i][j] csak az aktuális és az előző sor értékétől függ DP . Tehát a tér összetettségének optimalizálása érdekében egyetlen 1D tömböt használunk a számítások tárolására.
A megvalósítás lépései:
- Hozzon létre egy 1D vektort dp méretű m+1 .
- Állítson be egy alapesetet az értékeinek inicializálásával DP .
- Most ismételje meg a részproblémákat a beágyazott ciklus segítségével, és kapja meg az aktuális értéket a korábbi számításokból.
- Most hozzon létre egy ideiglenes 1d vektort prev_dp a korábbi számításokból származó aktuális értékek tárolására szolgál.
- Minden iteráció után rendelje hozzá az értékét prev_dp dp-re a további iterációhoz.
- Változó inicializálása res a végső válasz tárolására és frissítésére a Dp-n keresztüli iterációval.
- Végül térjen vissza, és nyomtassa ki a tárolt végső választ res .
Végrehajtás:
#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
Kimenet
Minimum adjustment cost is 75
Időbeli összetettség: O(n*m 2 )
Kiegészítő tér: O (m)
