Venta de Bob (reordenamiento de pares con restricciones para minimizar la suma de productos)

Hace un tiempo hice esta pregunta sobre Stack Overflow: Problema: la venta de Bob . Alguien sugirió publicar la pregunta aquí también.

Alguien ya ha hecho una pregunta relacionada con este problema aquí: peso mínimo por debajo del bosque de la cardinalidad dada , pero, por lo que entiendo, no me ayuda con mi problema. También vale la pena ver la respuesta mejor calificada en StackOverflow.

Aquí está la copia literal de mi pregunta de StackOverflow. Probablemente esté formulado de manera inadecuada para este sitio (diablos, me siento inadecuadamente sin educación solo preguntándolo aquí), así que siéntase libre de editarlo:

Nota: esta es una redacción abstracta de un problema de la vida real con respecto al pedido de registros en un archivo SWF. Una solución me ayudará a mejorar una aplicación de código abierto.

Bob tiene una tienda y quiere hacer una venta. Su tienda tiene una serie de productos, y tiene una cierta cantidad entera de unidades de cada producto en stock. También tiene una serie de etiquetas de precios montadas en estantes (tanto como la cantidad de productos), con los precios ya impresos en ellas. Puede colocar cualquier etiqueta de precio en cualquier producto (precio unitario para un artículo para todo su stock de ese producto), sin embargo, algunos productos tienen una restricción adicional: cualquier producto de este tipo puede no ser más barato que cierto otro producto.

Debe encontrar cómo organizar las etiquetas de precios, de modo que el costo total de todas las mercancías de Bob sea lo más bajo posible. El costo total es la suma de la etiqueta de precio asignada de cada producto multiplicada por la cantidad de ese producto en stock.

Dado:

• N - el número de productos y etiquetas de precios
• S _i , 0≤ i <N - la cantidad en stock del producto con índice i (entero)
• P _j , 0≤ j <N - el precio en la etiqueta de precio con índice j (entero)
• K - el número de pares de restricciones adicionales
• A _k , B _k , 0≤ k <K - índices de producto para la restricción adicional
  • Cualquier índice de producto puede aparecer como máximo una vez en B. Por lo tanto, el gráfico formado por esta lista de adyacencia es en realidad un conjunto de árboles dirigidos.

El programa debe encontrar:

• M _i , 0≤ i <N - asignación del índice del producto al índice de la etiqueta de precio (P _{M i} es el precio del producto i )

Para satisfacer las condiciones:

1. P _{M A k} ≤ P _{M B k} , para 0≤ k <K
2. Σ (S _i × P _{M i} ) para 0≤ i <N es mínimo

Tenga en cuenta que si no fuera por la primera condición, la solución sería simplemente ordenar las etiquetas por precio y productos por cantidad, y hacer coincidir ambos directamente.

Los valores típicos para la entrada serán N, K <10000. En el problema de la vida real, solo hay varias etiquetas de precio distintas (1,2,3,4).

Aquí hay un ejemplo de por qué las soluciones más simples (incluida la clasificación topológica) no funcionarán:

$\$$$\$$

La solución óptima es:

Price, $   1  2  3  4  5  6  7  8  9 10
Qty        9  8  7  6  1 10  5  4  3  2

con un costo total de 249. Si coloca el par 1,10 cerca de cualquier extremo, el costo total será mayor.$\$$

También publiqué esto en su pregunta original en Stack Overflow:

El problema es NP-completo para el caso general. Esto se puede mostrar a través de una reducción de 3 particiones (que es una versión NP-complete aún sólida de empaque de contenedores).

Supongamos que w ₁ , ..., w _n son los pesos de los objetos de la instancia de 3 particiones, que b es el tamaño del contenedor y k = n / 3 el número de contenedores que se pueden llenar. Por lo tanto, hay una partición de 3 si los objetos se pueden dividir de manera que haya exactamente 3 objetos por contenedor.

Para la reducción, fijamos N = kb y cada bin está representado por b etiquetas de precio del mismo precio (pensamos de P _i aumentando cada b º etiqueta). Sea t _i , 1≤ i ≤ k , el precio de las etiquetas correspondientes al i th bin. Para cada w _i tenemos un producto S _j de cantidad w _i + 1 (llamemos a esto el producto raíz de w _i ) y otro w _i - 1 productos de cantidad 1 que deben ser más baratos que S _j (Llame a estos productos de licencia).

Para t _i = (2b + 1) ⁱ , 1≤ i ≤ k , hay una partición de 3 si y solo si Bob puede vender por 2b Σ _{1≤ i ≤ k} t _i :

• Si hay una solución para 3 particiones, entonces todos los productos b correspondientes a los objetos w _i , w _j , w _l que se asignan al mismo contenedor se pueden etiquetar con el mismo precio sin violar las restricciones. Por lo tanto, la solución ha costado 2b Σ _{1≤ i ≤ k} t _i (ya que la cantidad total de productos con precio t _i es 2b ).
  
• Considere una solución óptima de la venta de Bob. Primero observe que en cualquier solución, más de 3 productos de raíz comparten la misma etiqueta de precio, por cada producto de raíz que es "demasiado" hay una etiqueta de precio más barata que se adhiere a menos de 3 productos de raíz. Esto es peor que cualquier solución, ya que existen exactamente 3 productos raíz por etiqueta de precio (si existe).
  Ahora todavía puede haber una solución de Bob's Sale con 3 etiquetas raíz por precio, pero sus productos de licencia no usan las mismas etiquetas de precio (los contenedores se desbordan). Digamos que la etiqueta de precio más cara etiqueta un producto raíz de w _i que tiene un producto de licencia etiquetado más barato. Esto implica que las 3 etiquetas raíz w _i , w _j , w _letiquetado con el precio más caro no suman b . Por lo tanto, el costo total de los productos etiquetados con este precio es de al menos 2b + 1 .
  Por lo tanto, dicha solución tiene un costo t _k (2b + 1) + algún otro costo de asignación. Dado que el costo óptimo para una partición 3 existente es 2b Σ _{1≤ i ≤ k} t _i , tenemos que demostrar que el caso considerado es peor. Este es el caso si t _k > 2b Σ _{1≤ i ≤ k-1} t _i (tenga en cuenta que ahora es k-1 en la suma). Ajuste t _i= (2b + 1) ⁱ , 1≤ i ≤ k , este es el caso. Esto también es válido, si no el precio más caro es el "malo", pero cualquier otro.

Entonces, esta es la parte destructiva ;-) Sin embargo, si el número de diferentes etiquetas de precio es una constante, puede usar la programación dinámica para resolverlo en tiempo polinómico.

Este es un seguimiento de la respuesta de Gero . La idea es modificar su construcción para mostrar una fuerte dureza NP.

$t_i=(2b+1)^i$$t_i=i$$P=2b\sum_{1\leq i \leq k} t_i$

$w_i-1$$P$$P$

Por lo tanto, solo es posible lograr el premio reclamado, si todos los productos de hoja tienen el mismo premio que su producto raíz, lo que significa que existe una partición de 3.

$k$$f(k)\cdot n^{O(1)}$$n^{O(k)}$

También publicado en la pregunta original de desbordamiento de pila.

Esto suena como una pregunta de teoría de juegos. En ese caso, una solución muy simple de fuerza bruta es:

Supongamos que las restricciones representan algunos invariantes de la forma.

S-> AkSBk | AkBkS | SAkBk

La solución es seguir agregando las restricciones primero, y luego los elementos. Por ejemplo: Digamos n = 10 y hay 2 restricciones, A1B1 y A2B2. Luego, hay tres hijos en el nodo raíz (nivel 2). Cada uno de estos 3 nodos tendrá 7 hijos de nivel 3, cada uno de los 21 tendrá 6 en el nivel 4, etc. Esencialmente, está ejecutando todas las combinaciones posibles.

                A1B1 --- Nivel 1 
               / | \
              / | \
             / | \
            / | \
    A1A2B2A1 A1B1A2B2 A2B2A1B1 --- Nivel 2

y hacer crecer el árbol. Aunque al principio parece una solución horrible, siento que podrías abandonar perseguir hojas muy caras usando algunas heurísticas y podas ...