Nájdite minimálne náklady na úpravu poľa
Vyskúšajte to na GfG Practice 
#practiceLinkDiv { display: none !important; }
Výstup
#practiceLinkDiv { display: none !important; } Dané pole kladných celých čísel nahradí každý prvok v poli tak, aby rozdiel medzi susednými prvkami v poli bol menší alebo rovný danému cieľu. Musíme minimalizovať náklady na úpravu, ktoré sú súčtom rozdielov medzi novými a starými hodnotami. V podstate musíme minimalizovať ?|A[i] - A nové [i]| kde 0? ja n-1 n je veľkosť A[] a A nové [] je pole so susedným rozdielom menším alebo rovným ako cieľ. Predpokladajme, že všetky prvky poľa sú menšie ako konštanta M = 100.
Príklady:
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 Nájdite minimálne náklady na úpravu poľa Skúste to!Aby sa minimalizovali náklady na úpravu ?|A[i] – A nové [i]| pre všetky indexy i v poli |A[i] - A nové [i]| by mala byť čo najbližšie k nule. Tiež |A[i] - A nové [i+1] ]| ? Cieľ.
Tento problém je možné vyriešiť pomocou dynamické programovanie .Nech dp[i][j] definuje minimálne náklady na úpravu pri zmene A[i] na j, potom vzťah DP je definovaný -
dp[i][j] = min{dp[i - 1][k]} + |j - A[i]|
for all k's such that |k - j| ? target
Tu 0? ja n a 0? j? M kde n je počet prvkov v poli a M = 100. Všetky k musíme uvažovať tak, že max(j - cieľ 0) ? k ? min (M j + cieľ)
Nakoniec minimálne náklady na úpravu poľa budú min{dp[n - 1][j]} pre všetkých 0 ? j? M.Algoritmus:
- Vytvorte 2D pole s inicializáciami dp[n][M+1], aby ste zaznamenali najnižšie náklady na úpravu zmeny A[i] na j, kde n je dĺžka poľa a M je jeho maximálna hodnota.
- Vypočítajte najmenšie náklady na úpravu zmeny A[0] na j pre prvý prvok poľa dp[0][j] pomocou vzorca dp[0][j] = abs (j - A[0]).
- Nahraďte A[i] za j v zostávajúcich prvkoch poľa dp[i][j] a použite vzorec dp[i][j] = min(dp[i-1][k] + abs(A[i] - j)), kde k má všetky možné hodnoty medzi max(j-cieľ0) a min(Mj+cieľ), aby ste získali minimálne náklady na úpravu.
- Ako minimálne náklady na úpravu uveďte najnižšie číslo z posledného riadku tabuľky dp.
Nižšie je uvedená implementácia vyššie uvedenej myšlienky:
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. ?>
Výstup
Minimum adjustment cost is 75
Časová zložitosť: O(n*m 2 )
Pomocný priestor: O(n *m)
Efektívny prístup: Optimalizácia priestoru
V predchádzajúcom prístupe aktuálna hodnota dp[i][j] závisí iba od aktuálnych a predchádzajúcich hodnôt riadkov DP . Aby sme optimalizovali zložitosť priestoru, používame na ukladanie výpočtov jediné 1D pole.
Kroky implementácie:
- Vytvorte 1D vektor dp veľkosti m+1 .
- Nastavte základný prípad inicializáciou hodnôt DP .
- Teraz iterujte cez podproblémy pomocou vnorenej slučky a získajte aktuálnu hodnotu z predchádzajúcich výpočtov.
- Teraz vytvorte dočasný 1d vektor prev_dp slúži na uloženie aktuálnych hodnôt z predchádzajúcich výpočtov.
- Po každej iterácii priraďte hodnotu prev_dp na dp pre ďalšiu iteráciu.
- Inicializujte premennú res uložiť konečnú odpoveď a aktualizovať ju opakovaním cez Dp.
- Nakoniec sa vráťte a vytlačte konečnú odpoveď uloženú v res .
Implementácia:
#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
Výstup
Minimum adjustment cost is 75
Časová zložitosť: O(n*m 2 )
Pomocný priestor: O (m)
