#practiceLinkDiv { display: ingen !viktigt; }Givet en array av positiva heltal ersätt varje element i arrayen så att skillnaden mellan intilliggande element i arrayen är mindre än eller lika med ett givet mål. Vi behöver minimera omställningskostnaden som är summan av skillnader mellan nya och gamla värden. Vi måste i princip minimera ?|A[i] - Any[i]| var 0? jag ? n-1 n är storleken på A[] och Any[] är matrisen med intilliggande skillnad mindre än eller lika med målet. Antag att alla element i arrayen är mindre än konstant M = 100.
Exempel:
Input: arr = [1 3 0 3] target = 1Recommended Practice Hitta lägsta justeringskostnad för en array Prova!
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]
För att minimera anpassningskostnaden ?|A[i] - Any[i]| för alla index i i arrayen |A[i] - Any[i]| bör vara så nära noll som möjligt. Även |A[i] - Any[i+1] ]| ? Mål.
Detta problem kan lösas genom dynamisk programmering .
vad är uri
Låt dp[i][j] definiera minimal justeringskostnad vid ändring av A[i] till j, då definieras DP-relationen av -
dp[i][j] = min{dp[i - 1][k]} + |j - A[i]|
for all k's such that |k - j| ? target
Här 0? jag ? n och 0? j ? M där n är antalet element i arrayen och M = 100. Vi måste betrakta alla k så att max(j - mål 0) ? k ? min(M j + mål)
Slutligen kommer den lägsta justeringskostnaden för arrayen att vara min{dp[n - 1][j]} för alla 0 ? j ? M.
Algoritm:
- Skapa en 2D-matris med initialiseringarna dp[n][M+1] för att registrera den lägsta justeringskostnaden för att ändra A[i] till j där n är matrisens längd och M är dess maximala värde.
- Beräkna den minsta justeringskostnaden för att ändra A[0] till j för det första elementet i matrisen dp[0][j] med hjälp av formeln dp[0][j] = abs (j - A[0]).
- Byt ut A[i] med j i de återstående arrayelementen dp[i][j] och använd formeln dp[i][j] = min(dp[i-1][k] + abs(A[i] - j)) där k tar alla möjliga värden mellan max(j-target0) och min(Mj+target) för att få den minimala justeringskostnaden.
- Som lägsta justeringskostnad anger du det lägsta antalet från den sista raden i dp-tabellen.
Nedan är implementeringen av ovanstående idé:
C++// C++ program to find minimum adjustment cost of an array #include
// 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 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# 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.
<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 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. ?> Produktion
Minimum adjustment cost is 75
Tidskomplexitet: O(n*m2)
Hjälputrymme: O(n *m)
Effektivt tillvägagångssätt: Utrymmesoptimering
I tidigare tillvägagångssätt det aktuella värdet dp[i][j] är bara beroende av nuvarande och föregående radvärden för DP . Så för att optimera rymdkomplexiteten använder vi en enda 1D-array för att lagra beräkningarna.
java hur man åsidosätter
Implementeringssteg:
- Skapa en 1D-vektor dp av storlek m+1 .
- Ställ in ett basfall genom att initiera värdena för DP .
- Iterera nu över delproblem med hjälp av kapslad loop och få det aktuella värdet från tidigare beräkningar.
- Skapa nu en tillfällig 1d-vektor prev_dp används för att lagra aktuella värden från tidigare beräkningar.
- Efter varje iteration tilldela värdet av prev_dp till dp för ytterligare iteration.
- Initiera en variabel res för att lagra det slutliga svaret och uppdatera det genom att iterera genom Dp.
- Äntligen returnera och skriv ut det slutliga svaret lagrat i res .
Genomförande:
#include
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)); } }
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))
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)); } }
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
Produktion
Minimum adjustment cost is 75
Tidskomplexitet: O(n*m2)
Hjälputrymme: O (m)
fel: kunde inte hitta eller ladda huvudklassen