#practiceLinkDiv { display: ingen !important; }Givet et array af positive heltal skal hvert element i arrayet erstattes, således at forskellen mellem tilstødende elementer i arrayet er mindre end eller lig med et givet mål. Vi er nødt til at minimere tilpasningsomkostningerne, der er summen af forskelle mellem nye og gamle værdier. Vi er grundlæggende nødt til at minimere ?|A[i] - Any[i]| hvor 0? jeg ? n-1 n er størrelsen af A[] og Any[] er arrayet med tilstødende forskel mindre end eller lig med målet. Antag, at alle elementer i arrayet er mindre end konstant M = 100.
cout
Eksempler:
Input: arr = [1 3 0 3] target = 1Recommended Practice Prøv det!
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]
For at minimere tilpasningsomkostningerne ?|A[i] - Any[i]| for alle indeks i i arrayet |A[i] - Any[i]| skal være så tæt på nul som muligt. Også |A[i] - Any[i+1] ]| ? Mål.
Dette problem kan løses ved dynamisk programmering .
Lad dp[i][j] definere minimale justeringsomkostninger ved at ændre A[i] til j, så er DP-relationen defineret ved -
dp[i][j] = min{dp[i - 1][k]} + |j - A[i]|
for all k's such that |k - j| ? target
Her 0? jeg ? n og 0? j ? M hvor n er antallet af elementer i arrayet og M = 100. Vi skal betragte alle k sådan, at max(j - target 0) ? k ? min(M j + mål)
Endelig vil minimumsjusteringsomkostningerne for arrayet være min{dp[n - 1][j]} for alle 0 ? j ? M.
Algoritme:
- Opret et 2D-array med initialiseringerne dp[n][M+1] for at registrere de mindste justeringsomkostninger ved at ændre A[i] til j, hvor n er arrayets længde og M er dens maksimale værdi.
- Beregn den mindste justeringsomkostning ved at ændre A[0] til j for det første element i arrayet dp[0][j] ved at bruge formlen dp[0][j] = abs (j - A[0]).
- Erstat A[i] med j i de resterende array-elementer dp[i][j] og brug formlen dp[i][j] = min(dp[i-1][k] + abs(A[i] - j)), hvor k tager alle mulige værdier mellem max(j-target0) og min(Mj+target) for at få den minimale justeringsomkostning.
- Som minimumsjusteringsomkostning angives det laveste tal fra den sidste række i dp-tabellen.
Nedenfor er implementeringen af ovenstå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
Tidskompleksitet: O(n*m2)
Hjælpeplads: O(n *m)
Effektiv tilgang: Pladsoptimering
I tidligere tilgang den aktuelle værdi dp[i][j] er kun afhængig af de nuværende og forrige rækkeværdier af DP . Så for at optimere pladskompleksiteten bruger vi et enkelt 1D-array til at gemme beregningerne.
Implementeringstrin:
- Opret en 1D vektor dp af størrelse m+1 .
- Indstil et basistilfælde ved at initialisere værdierne af DP .
- Gentag nu over underproblemer ved hjælp af indlejret løkke og få den aktuelle værdi fra tidligere beregninger.
- Opret nu en midlertidig 1d vektor prev_dp bruges til at gemme de aktuelle værdier fra tidligere beregninger.
- Tildel værdien efter hver iteration prev_dp til dp for yderligere iteration.
- Initialiser en variabel res at gemme det endelige svar og opdatere det ved at gentage Dp.
- Til sidst returner og udskriv det endelige svar gemt i res .
Implementering:
#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
Tidskompleksitet: O(n*m2)
Hjælpeplads: O (m)