#practiceLinkDiv { display: none !important; }Zadano je polje pozitivnih cijelih brojeva, zamijenite svaki element u nizu tako da je razlika između susjednih elemenata u nizu manja ili jednaka danom cilju. Moramo minimizirati trošak prilagodbe koji je zbroj razlika između novih i starih vrijednosti. U osnovi trebamo minimizirati ?|A[i] - Anovi[i]| gdje 0? ja ? n-1 n je veličina A[] i Anovi[] je polje sa susjednom razlikom manjom ili jednakom cilju. Pretpostavimo da su svi elementi niza manji od konstante M = 100.
Primjeri:
Input: arr = [1 3 0 3] target = 1Recommended Practice Pronađite minimalni trošak prilagodbe niza Probajte!
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]
Kako bi se smanjio trošak prilagodbe ?|A[i] - Anovi[i]| za sve indekse i u nizu |A[i] - Anovi[i]| treba biti što bliže nuli. Također |A[i] - Anovi[i+1] ]| ? Cilj.
Ovaj se problem može riješiti pomoću dinamičko programiranje .
Neka dp[i][j] definira minimalni trošak prilagodbe na promjenu A[i] u j tada je DP relacija definirana s -
dp[i][j] = min{dp[i - 1][k]} + |j - A[i]|
for all k's such that |k - j| ? target
Ovdje 0? ja ? n i 0? j ? M gdje je n broj elemenata u nizu i M = 100. Moramo uzeti u obzir sve k tako da max(j - cilj 0) ? k ? min (M j + cilj)
Konačno, minimalni trošak prilagodbe niza bit će min{dp[n - 1][j]} za sve 0 ? j ? M.
Algoritam:
- Napravite 2D niz s inicijalizacijama dp[n][M+1] kako biste zabilježili najmanji trošak prilagodbe promjene A[i] u j gdje je n duljina niza, a M njegova najveća vrijednost.
- Izračunajte najmanji trošak prilagodbe promjene A[0] u j za prvi element niza dp[0][j] pomoću formule dp[0][j] = abs (j - A[0]).
- Zamijenite A[i] s j u preostalim elementima niza dp[i][j] i upotrijebite formulu dp[i][j] = min(dp[i-1][k] + abs(A[i] - j)) gdje k uzima sve moguće vrijednosti između max(j-target0) i min(Mj+target) da biste dobili minimalni trošak prilagodbe.
- Kao minimalni trošak prilagodbe navedite najniži broj iz zadnjeg retka dp tablice.
Ispod je implementacija gore navedene ideje:
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. ?> Izlaz
Minimum adjustment cost is 75
Vremenska složenost: O(n*m2)
Pomoćni prostor: O(n *m)
Učinkovit pristup: Optimizacija prostora
U prethodnom pristupu trenutna vrijednost dp[i][j] ovisi samo o trenutnim i prethodnim vrijednostima retka DP . Dakle, kako bismo optimizirali složenost prostora, koristimo jedno 1D polje za pohranjivanje izračuna.
Koraci implementacije:
- Napravite 1D vektor dp veličine m+1 .
- Postavite osnovni slučaj inicijaliziranjem vrijednosti DP .
- Sada iterirajte podprobleme uz pomoć ugniježđene petlje i dohvatite trenutnu vrijednost iz prethodnih izračuna.
- Sada stvorite privremeni 1d vektor prethodni_dp koristi se za pohranjivanje trenutnih vrijednosti iz prethodnih izračuna.
- Nakon svake iteracije dodijelite vrijednost prethodni_dp na dp za daljnje ponavljanje.
- Inicijalizirati varijablu res za pohranjivanje konačnog odgovora i njegovo ažuriranje ponavljanjem kroz Dp.
- Na kraju se vratite i ispišite konačni odgovor pohranjen u res .
Implementacija:
#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
Izlaz
Minimum adjustment cost is 75
Vremenska složenost: O(n*m2)
Pomoćni prostor: O (m)