Programa C# para cortar una varilla | DP-13

Dada una barra de n pulgadas de longitud y una array de precios que contiene los precios de todas las piezas de tamaño menor que n. Determine el valor máximo que se puede obtener cortando la varilla y vendiendo las piezas. Por ejemplo, si la longitud de la varilla es 8 y los valores de las diferentes piezas se dan a continuación, entonces el valor máximo que se puede obtener es 22 (cortando dos piezas de longitud 2 y 6) 

length   | 1   2   3   4   5   6   7   8  
--------------------------------------------
price    | 1   5   8   9  10  17  17  20

Y si los precios son los siguientes, entonces el valor máximo que se puede obtener es 24 (cortando en ocho piezas de longitud 1)

length   | 1   2   3   4   5   6   7   8  
--------------------------------------------
price    | 3   5   8   9  10  17  17  20

A continuación se muestra una implementación recursiva simple del problema de Rod Cutting. La implementación simplemente sigue la estructura recursiva mencionada anteriormente.

// A Naive recursive solution for
// Rod cutting problem
using System;
class GFG {
 
    /* Returns the best obtainable
       price for a rod of length
       n and price[] as prices of
       different pieces */
    static int cutRod(int[] price, int n)
    {
        if (n <= 0)
            return 0;
        int max_val = int.MinValue;
 
        // Recursively cut the rod in
        // different pieces and compare
        // different configurations
        for (int i = 0; i < n; i++)
            max_val = Math.Max(max_val, price[i] + cutRod(price, n - i - 1));
 
        return max_val;
    }
 
    // Driver Code
    public static void Main()
    {
        int[] arr = new int[] { 1, 5, 8, 9, 10, 17, 17, 20 };
        int size = arr.Length;
        Console.WriteLine("Maximum Obtainable Value is " + cutRod(arr, size));
    }
}
 
// This code is contributed by Sam007

Maximum Obtainable Value is 22

Teniendo en cuenta la implementación anterior, el siguiente es un árbol de recursión para un Rod de longitud 4.

cR() ---> cutRod() 

                             cR(4)
                  /        /           
                 /        /              
             cR(3)       cR(2)     cR(1)   cR(0)
            /  |         /         |
           /   |        /          |  
      cR(2) cR(1) cR(0) cR(1) cR(0) cR(0)
     /        |          |
    /         |          |   
  cR(1) cR(0) cR(0)      cR(0)
   /
 /
CR(0)

En el árbol de recursión parcial anterior, cR(2) se resuelve dos veces. Podemos ver que hay muchos subproblemas que se resuelven una y otra vez. Dado que los mismos subproblemas se vuelven a llamar, este problema tiene la propiedad Superposición de subproblemas. Entonces, el problema de Rod Cutting tiene ambas propiedades (ver this y this ) de un problema de programación dinámica. Al igual que otros problemas típicos de programación dinámica (DP) , los cálculos de los mismos subproblemas se pueden evitar mediante la construcción de una array temporal val[] de forma ascendente.

// A Dynamic Programming solution
// for Rod cutting problem
using System;
class GFG {
 
    /* Returns the best obtainable
       price for a rod of length n
       and price[] as prices of
       different pieces */
    static int cutRod(int[] price, int n)
    {
        int[] val = new int[n + 1];
        val[0] = 0;
 
        // Build the table val[] in
        // bottom up manner and return
        // the last entry from the table
        for (int i = 1; i <= n; i++) {
            int max_val = int.MinValue;
            for (int j = 0; j < i; j++)
                max_val = Math.Max(max_val,
                                   price[j] + val[i - j - 1]);
            val[i] = max_val;
        }
 
        return val[n];
    }
 
    // Driver Code
    public static void Main()
    {
        int[] arr = new int[] { 1, 5, 8, 9, 10, 17, 17, 20 };
        int size = arr.Length;
        Console.WriteLine("Maximum Obtainable Value is " + cutRod(arr, size));
    }
}
 
// This code is contributed by Sam007

Maximum Obtainable Value is 22

Consulte el artículo completo sobre Cortar una varilla | DP-13 para más detalles!