Se nos da un conjunto de frutas. Cada fruta tiene un precio y un contenido de vitaminas ; asociamos la fruta con el par ordenado . Ahora tenemos que organizar estas frutas de tal manera que la lista ordenada contenga los precios en orden ascendente y el contenido de vitaminas en orden descendente.
Ejemplo 1 : y .
Si organizamos la lista de manera que todos los precios estén en orden ascendente y los contenidos de vitaminas en orden descendente, las listas válidas son las siguientes:
De las listas anteriores, quiero elegir la lista de tamaño máximo. Si más de una lista tiene un tamaño máximo, deberíamos elegir la lista de tamaño máximo cuya suma de precios sea menor. La lista que debe elegirse en el ejemplo anterior es .
Ejemplo 2 : y
La respuesta a este ejemplo de ejemplo es .
Hasta ahora, esto es lo que he estado haciendo:
- Ordene la lista original en orden ascendente de precio;
- Encuentra todas las subsecuencias de la lista ordenada;
- Compruebe si la subsecuencia es válida y compare todas las subsecuencias válidas.
Sin embargo, esto lleva tiempo exponencial; ¿Cómo puedo resolver este problema de manera más eficiente?