dynamic-programming
Cięcie prętów
Szukaj…
Cięcie pręta, aby uzyskać maksymalny zysk
Biorąc pod uwagę pręt o długości n cali i tablicę długości m cen, która zawiera ceny wszystkich sztuk mniejszych niż n. Musimy znaleźć maksymalną wartość możliwą do uzyskania przez cięcie pręta i sprzedaż elementów. Na przykład, jeśli długość pręta wynosi 8, a wartości różnych elementów podano w następujący sposób, to maksymalna możliwa do uzyskania wartość wynosi 22 .
+---+---+---+---+---+---+---+---+
(price)| 1 | 5 | 8 | 9 | 10| 17| 17| 20|
+---+---+---+---+---+---+---+---+
Użyjemy tablicy 2D dp [m] [n + 1], gdzie n jest długością pręta, a m jest długością tablicy cen. W naszym przykładzie potrzebujemy dp [8] [9] . Tutaj dp [i] [j] będzie oznaczać cenę maksymalną, sprzedając wędkę o długości j. Możemy mieć maksymalną wartość długości j jako całości lub moglibyśmy złamać długość, aby zmaksymalizować zysk.
Na początku dla kolumny 0 nic to nie przyczyni, dlatego oznaczenie wszystkich wartości jako 0. Wszystkie wartości 0 kolumny będą wynosić 0. Dla dp [0] [1] , jaka jest maksymalna wartość, którą możemy uzyskać sprzedawany pręt o długości 1. Będzie to 1. Podobnie jak w przypadku pręta o długości 2 dp [0] [2] możemy mieć 2 (1 + 1). Trwa to do dp [0] [8] . Więc po pierwszej iteracji będzie wyglądać nasza tablica dp [].
+---+---+---+---+---+---+---+---+---+
(price)| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
+---+---+---+---+---+---+---+---+---+
(1) 1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 9 |
+---+---+---+---+---+---+---+---+---+
(5) 2 | 0 | | | | | | | | |
+---+---+---+---+---+---+---+---+---+
(8) 3 | 0 | | | | | | | | |
+---+---+---+---+---+---+---+---+---+
(9) 4 | 0 | | | | | | | | |
+---+---+---+---+---+---+---+---+---+
(10) 5 | 0 | | | | | | | | |
+---+---+---+---+---+---+---+---+---+
(17) 6 | 0 | | | | | | | | |
+---+---+---+---+---+---+---+---+---+
(17) 7 | 0 | | | | | | | | |
+---+---+---+---+---+---+---+---+---+
(20) 8 | 0 | | | | | | | | |
+---+---+---+---+---+---+---+---+---+
W przypadku dp [2] [2] zadajmy sobie pytanie, co jest najlepsze, co mogę uzyskać, jeśli połamię pręt na dwie części (1,1) lub wezmę pręt jako całość (długość = 2). że jeśli połamię pręt na dwie części, maksymalny zysk, jaki mogę osiągnąć, to 2, a jeśli mam pręt jako całość, mogę go sprzedać za 5. Po drugiej iteracji tablica dp będzie wyglądać następująco:
+---+---+---+---+---+---+---+---+---+
(price)| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
+---+---+---+---+---+---+---+---+---+
(1) 1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 9 |
+---+---+---+---+---+---+---+---+---+
(5) 2 | 0 | 1 | 5 | 6 | 10| 11| 15| 16| 20|
+---+---+---+---+---+---+---+---+---+
(8) 3 | 0 | | | | | | | | |
+---+---+---+---+---+---+---+---+---+
(9) 4 | 0 | | | | | | | | |
+---+---+---+---+---+---+---+---+---+
(10) 5 | 0 | | | | | | | | |
+---+---+---+---+---+---+---+---+---+
(17) 6 | 0 | | | | | | | | |
+---+---+---+---+---+---+---+---+---+
(17) 7 | 0 | | | | | | | | |
+---+---+---+---+---+---+---+---+---+
(20) 8 | 0 | | | | | | | | |
+---+---+---+---+---+---+---+---+---+
Aby obliczyć dp [i] [j] nasza formuła będzie wyglądać następująco:
if j>=i
dp[i][j] = Max(dp[i-1][j], price[i]+arr[i][j-i]);
else
dp[i][j] = dp[i-1][j];
Po ostatniej iteracji będzie wyglądała nasza tablica dp []
+---+---+---+---+---+---+---+---+---+
(price)| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
+---+---+---+---+---+---+---+---+---+
(1) 1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 9 |
+---+---+---+---+---+---+---+---+---+
(5) 2 | 0 | 1 | 5 | 6 | 10| 11| 15| 16| 20|
+---+---+---+---+---+---+---+---+---+
(8) 3 | 0 | 1 | 5 | 8 | 10| 13| 16| 18| 21|
+---+---+---+---+---+---+---+---+---+
(9) 4 | 0 | 1 | 5 | 8 | 10| 13| 16| 18| 21|
+---+---+---+---+---+---+---+---+---+
(10) 5 | 0 | 1 | 5 | 8 | 10| 13| 16| 18| 21|
+---+---+---+---+---+---+---+---+---+
(17) 6 | 0 | 1 | 5 | 8 | 10| 13| 17| 18| 22|
+---+---+---+---+---+---+---+---+---+
(17) 7 | 0 | 1 | 5 | 8 | 10| 13| 17| 18| 22|
+---+---+---+---+---+---+---+---+---+
(20) 8 | 0 | 1 | 5 | 8 | 10| 13| 17| 18| 22|
+---+---+---+---+---+---+---+---+---+
Otrzymamy wynik w dp [n] [m + 1] .
Implementacja w Javie
public int getMaximumPrice(int price[],int n){
int arr[][] = new int[n][price.length+1];
for(int i=0;i<n;i++){
for(int j=0;j<price.length+1;j++){
if(j==0 || i==0)
arr[i][j] = 0;
else if(j>=i){
arr[i][j] = Math.max(arr[i-1][j], price[i-1]+arr[i][j-i]);
}else{
arr[i][j] = arr[i-1][j];
}
}
}
return arr[n-1][price.length];
}
Złożoność czasu
O(n^2)