dynamic-programming
Режущий инструмент
Поиск…
Резка стержня, чтобы получить максимальную прибыль
Для стержня длиной n дюймов и массива длины m цен, который содержит цены на все куски размером меньше n. Мы должны найти максимальное значение, получаемое путем разрезания стержня и продажи кусков. Например, если длина стержня равна 8, а значения разных кусков указаны следующим образом, тогда максимально допустимое значение равно 22 .
+---+---+---+---+---+---+---+---+
(price)| 1 | 5 | 8 | 9 | 10| 17| 17| 20|
+---+---+---+---+---+---+---+---+
Мы будем использовать 2D-массив dp [m] [n + 1], где n - длина стержня, а m - длина ценового массива. Для нашего примера нам понадобится dp [8] [9] . Здесь dp [i] [j] будет обозначать максимальную цену, продавая стержень длины j. Мы можем иметь максимальное значение длины j в целом или мы могли бы сломать длину, чтобы максимизировать прибыль.
Сначала для 0-го столбца он ничего не внесет, поэтому все значения будут равны 0. Таким образом, все значения 0-го столбца будут равны 0. Для dp [0] [1] , какое максимальное значение мы можем получить на продавая стержень длины 1.It будет 1. Аналогично для стержня длины 2 dp [0] [2] мы можем иметь 2 (1 + 1). Это продолжается до dp [0] [8]. После первой итерации наш массив 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 | | | | | | | | |
+---+---+---+---+---+---+---+---+---+
Для dp [2] [2] мы должны спросить себя, что самое лучшее, что я могу получить, если разбить стержень на две части (1,1) или взять стержень в целом (длина = 2). Мы можем видеть что если я сломаю стержень на две части, максимальная прибыль, которую я могу сделать, равна 2, и если у меня есть стержень в целом, я могу продать его для 5. После второй итерации массив 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 | | | | | | | | |
+---+---+---+---+---+---+---+---+---+
(9) 4 | 0 | | | | | | | | |
+---+---+---+---+---+---+---+---+---+
(10) 5 | 0 | | | | | | | | |
+---+---+---+---+---+---+---+---+---+
(17) 6 | 0 | | | | | | | | |
+---+---+---+---+---+---+---+---+---+
(17) 7 | 0 | | | | | | | | |
+---+---+---+---+---+---+---+---+---+
(20) 8 | 0 | | | | | | | | |
+---+---+---+---+---+---+---+---+---+
Поэтому для вычисления dp [i] [j] наша формула будет выглядеть так:
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];
После последней итерации наш массив 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|
+---+---+---+---+---+---+---+---+---+
Мы получим результат при dp [n] [m + 1] .
Реализация на Java
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];
}
Сложность времени
O(n^2)