Encuentra subsecuencia de longitud máxima satisfacer simultáneamente dos limitaciones de pedidos

Question

Se nos da un conjunto $ F = \ {f_1, f_2, F_3, ..., f_n \} $ de $ N $ Frutas. Cada fruta tiene precio $ P_i $ y el contenido de vitamina v_i $ $; que la fruta asociada $ $ f_i con el par ordenado $ (P_i, v_i) $. Ahora tenemos que arreglar estos frutos de tal manera que la lista ordenada contiene precios en orden ascendente contenido de la orden y de la vitamina en orden descendente.

Ejemplo 1 : $ N = 4 $ y $ F = \ {(2, 8), (5, 11), (7, 9), (10, 2) \} $ .

Si ordenamos la lista de tal manera que todos los precios están en orden ascendente contenido de la orden y de la vitamina en orden descendente, a continuación, las listas vigentes son los siguientes:

• $ [(2, 8)] $
• $ [(5, 11)] $
• $ [(7, 9)] $
• $ [(10, 2)] $
• $ [(2, 8), (10, 2)] $
• $ [(5, 11), (7, 9)] $
• $ [(5, 11), (10, 2)] $
• $ [(7, 9), (10, 2)] $
• $ [(5, 11), (7, 9), (10, 2)] $

A partir de la lista de arriba, quiero que elegir la lista de tamaño máximo. Si más de una lista tiene tamaño máximo, debemos elegir la lista de tamaño máximo cuya suma de los precios es menos. La lista que debe ser elegido en el ejemplo anterior es $ \ {(5, 11), (7, 9), (10, 2) \} $.

Ejemplo 2 : $ N = 10 $ y $$ F = \ {(99,10), (12,23), (34,4), (10,5), ( 87,11), (19,10), \\ (90,18), (43,90), (13.100), (78,65) \} $$

La respuesta a este ejemplo de instancia es $ [(13100), (43,90), (78,65), (87,11), (99,10)] $.

Hasta ahora, esto es lo que he estado haciendo:

1. Ordenar la lista original en orden ascendente de precio;
2. Para todas las subsecuencias de la lista ordenada;
3. Compruebe si la subsecuencia es válida, y comparar todas las subsecuencias válidos.

Sin embargo, esto lleva tiempo exponencial; ¿Cómo puedo solucionar este problema de manera más eficiente?

Answer 1

Una solución de programación dinámica funcionaría aquí, si el contenido de vitaminas provienen de un conjunto finito (por ejemplo, los números enteros delimitadas). En primer lugar, ordenar las frutas en orden ascendente precio y en los casos eran dos o más frutas tienen el mismo precio, más o menos en ellos contenido en vitaminas (descendente). Ahora, defina $ M [f, v] $ a ser el máximo número de frutas en una lista secundaria, que contiene sólo el último $ f $ frutos (de la lista ordenada), que tiene un contenido de vitamina de a lo sumo $ v $. $ M [0, *] = 0 y $ $$ M [f, v] = \ begin {casos} \ Mathrm {max} \ {M [f-1, v], 1 + M [f-1, V_F] \} y \ text {if \ (V_F <= v \)} \\ M [f-1, v] y \ text {de otra manera} \\ \ end {casos} $$ El uso de programación dinámica que da una solución que se ejecuta en $ O (\ text {número de frutos} \ tiempos \ texto {} posibles valores vitamínicos) $.