dynamic-programming
Corte de varilla

Cortando la caña para obtener el máximo beneficio.

Dada una vara de longitud n pulgadas y una serie de longitud m de precios que contiene precios de todas las piezas de tamaño más pequeño que n. Tenemos que encontrar el valor máximo que se puede obtener cortando la barra y vendiendo las piezas. Por ejemplo, si la longitud de la varilla es 8 y los valores de las diferentes piezas se indican a continuación, el valor máximo obtenible es 22 .

       +---+---+---+---+---+---+---+---+
 (price)| 1 | 5 | 8 | 9 | 10| 17| 17| 20|
        +---+---+---+---+---+---+---+---+

Usaremos una matriz 2D dp [m] [n + 1] donde n es la longitud de la barra y m es la longitud de la matriz de precios. Para nuestro ejemplo, necesitaremos dp [8] [9] . Aquí dp [i] [j] indicará el precio máximo vendiendo la vara de longitud j. Podemos tener el valor máximo de longitud j en su totalidad o podríamos haber roto la longitud para maximizar el beneficio.

Al principio, para la columna 0, no aportará nada, por lo que marcará todos los valores como 0. Por lo tanto, todos los valores de la columna 0 serán 0. Para dp [0] [1] , ¿cuál es el valor máximo que podemos obtener? vendiendo varilla de longitud 1. Será 1. De manera similar para varilla de longitud 2 dp [0] [2] podemos tener 2 (1 + 1). Esto continúa hasta dp [0] [8] . Por lo tanto, después de la primera iteración nuestra matriz dp [] se verá como

      +---+---+---+---+---+---+---+---+---+
 (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 |   |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+---+

Para dp [2] [2] tenemos que preguntarnos qué es lo mejor que puedo obtener si rompo la varilla en dos piezas (1,1) o si tomo la varilla como un todo (longitud = 2). Podemos ver que si rompo la varilla en dos partes, el beneficio máximo que puedo obtener es 2 y si si tengo la varilla en su totalidad, puedo venderla por 5. Después de la segunda iteración, la matriz dp [] se verá así:

     +---+---+---+---+---+---+---+---+---+
 (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 |   |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+---+ 

Entonces para calcular dp [i] [j] nuestra fórmula se verá así:

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];

Después de la última iteración, nuestra matriz dp [] se verá como

       +---+---+---+---+---+---+---+---+---+
 (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|
        +---+---+---+---+---+---+---+---+---+

Tendremos el resultado en dp [n] [m + 1] .

Implementación en 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];
    }

Complejidad del tiempo

O(n^2)