programación dinámica y la aplicación de la mochila

Question

Im estudiar la programación dinámica y estoy buscando para resolver el siguiente problema, que se puede encontrar aquí http://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf:

Se le da un trozo de tela rectangular con dimensiones X por Y, donde X e Y son enteros positivos, y una lista de n productos que se pueden hacer usando la tela. Para cada producto i en [1, n] usted sabe que se necesita un rectángulo de tela de dimensiones ai por bi y que el precio de venta final del producto es ci. Supongamos que ai, bi y ci son enteros positivos. Usted tiene una máquina que puede cortar cualquier pieza rectangular de tela en dos piezas, ya sea horizontal o verticalmente. Diseñe un algoritmo que encuentre la mejor estrategia para cortar una pieza de tela X por Y para que los productos fabricados con las piezas resultantes den la suma máxima de los precios de venta. Puede hacer tantas copias de un producto determinado como desee o ninguna si lo desea. (De los algoritmos de Dasgupta, Papadimitriou y Vazirani.)

Parece que tenemos una especie de problema de mochila bidimensional, pero creo que es posible resolverlo simplemente con el algoritmo tradicional de mochila considerando el pesos como las áreas de los rectángulos. ¿Esto parece un enfoque razonable?

Esta es una asignación de programación para un curso que estoy tomando, por lo que solo incluya discusión conceptual y/o pseudocódigo para ilustrar ideas.

Answer 1

Creo que debe centrarse en el hecho de que la máquina corta la tela en dos piezas. ¿Qué puede caber en cada una de esas dos piezas? Considere lo siguiente:

+-------------+-------------------+ 
|    |  Piece B  | 
|    |     | 
| Piece A +----------+--------+ 
|    |   |  | 
|    |   |  | 
|    |   | Piece | 
+-------------+----------+ C | 
|      |  | 
|   Piece D  |  | 
+------------------------+--------+ 

Estos cuatro ajuste en la tela, pero no de una manera que es posible lograr con tres cortes. (Posiblemente un arreglo diferente permitiría que con estas piezas particulares, piense en esto como un diagrama conceptual, no a escala. Mis habilidades de arte ascii están limitadas hoy.)

Centrándose en "¿dónde está el corte?" Debería darle el solución de programación dinámica. Buena suerte.

Answer 2

Así que empiezas con un rectángulo X * Y. Supongamos que la solución óptima consiste en realizar un corte vertical (u horizontal), y luego tiene dos rectángulos nuevos con las dimensiones X * Y1 y X * Y2 con Y1 + Y2 = Y. Como desea maximizar sus ganancias, debe maximizar los beneficios en estos nuevos rectángulos (óptima subestructura). Por lo tanto, su recursión inicial es la siguiente: f(X, Y) = max(f(X, Y1) + f(X, Y2), f(X1, Y) + f(X2, Y)) para todos los valores posibles de X1, X2 (corte horizontal) y Y1, Y2 (corte vertical).

Ahora la pregunta es ¿cuándo realmente decido hacer un producto? Puede decidir crear un producto cuando una de sus dimensiones es igual a una de las dimensiones de su rectángulo actual (¿por qué? Porque si esto no se cumple y la solución óptima incluye fabricar este producto, tarde o temprano necesitará haga un corte vertical (u horizontal) y este caso ya se maneja en la recursión inicial), por lo que realiza el corte apropiado y tiene un nuevo rectángulo X * Y1 (o X1 * Y), dependiendo del corte que realizó para obtener el producto), en este caso, la recursión se convierte en f(X, Y) = cost of product + f(X1, Y).

La solución del problema original es f(X, Y). El tiempo de ejecución de esta solución dp sería O(X * Y * (X + Y + number of available products)): tiene X * Y rectángulos posibles, para cada uno de ellos prueba todos los cortes posibles (X + Y) e intenta hacer uno de los productos disponibles a partir de este rectángulo.

Además, vea este problema similar: Sharing Chocolate de las Finales Mundiales 2010 del ICPC.

Answer 3

Por favor, incluya las condiciones necesarias para el rectángulo de tamaño (0, something) o (something, 0) en la función Rect().

Answer 4

optimize() {

Rectangle memo[width][height] 
optimize(0,0,totalwidth, totalheight, memo) 

}

optimize (x, y, anchura, altura, memo) {

if memo[width][height] != null 
    return memo[width][height] 

rect = new Rectangle(width, height, value = 0) 
for each pattern { 

    //find vertical cut solution 
    leftVerticalRect = optimize (x, y + pattern.height, pattern.width, height-pattern.height,memo) 
    rightVerticalRect = optimize(x + pattern.width, y, width-pattern.width, height) 
    verticalcut = new Cut(x + pattern.width, y, x + pattern.width, y + height) 

    //find horizontal cut solution 
    topHorizontalRect = optimize (--parameters--) 
    bottomHortizonalRect = optimize(--parameters--) 
    horizontalcut = new Cut(--parameters--) 

    //see which solution is more optimal 
    if (leftVerticalRect.val + rightVerticalRect.val > topHorizontalRect.val + bottomHorizontalRect.val) 
     subprobsolution = vertical cut solution 
    else 
     subprobsolution = horizontal cut solution 

    //see if the solution found is greater than previous solutions to this subproblem 
    if (subprobsolution.value + pattern.value > rect.value) { 
     rect.subrect1 = subprobsolutionrect1 
     rect.subrect2 = subprobsolutionrect2 
     rect.pattern = pattern 
     rect.cut = subprobsolutioncut 
     rect.value = rect.subrect1.value + rect.subrect2.value + rect.pattern.value 
    } 
} 

memo[width][height] = rect 
return rect 

}