Trouver une sous-séquence de longueur maximale satisfaisant simultanément deux contraintes d'ordre

On nous donne un ensemble de Fruits. Chaque fruit a un prix et une teneur en vitamines ; nous avons associé le fruit à la paire ordonnée . Maintenant, nous devons organiser ces fruits de telle sorte que la liste triée contienne les prix en ordre croissant et le contenu en vitamines en ordre décroissant.$F=\{f_1, f_2, f_3, …, f_N\}$$N$$P_i$$V_i$$f_i$$(P_i, V_i)$

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

Si nous organisons la liste de manière à ce que tous les prix soient en ordre croissant et le contenu en vitamines en ordre décroissant, les listes valides sont les suivantes:

• $[(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)]$

Dans les listes ci-dessus, je souhaite choisir la liste de taille maximale. Si plusieurs listes ont une taille maximale, nous devons choisir la liste de taille maximale dont la somme des prix est la moins élevée. La liste qui doit être choisie dans l'exemple ci-dessus est .$\{(5, 11), (7, 9), (10, 2)\}$

Exemple 2 : $N = 10$ et

$$F = \{(99,10),(12,23),(34,4),(10,5),(87,11),(19,10), \\(90,18), (43,90),(13,100),(78,65)\}$$

La réponse à cet exemple d'instance est $[(13,100),(43,90),(78,65),(87,11),(99,10)]$ .

Jusqu'à présent, c'est ce que j'ai fait:

1. Trier la liste d'origine par ordre croissant de prix;
2. Trouver toutes les sous-séquences de la liste triée;
3. Vérifiez si la sous-séquence est valide et comparez toutes les sous-séquences valides.

Cependant, cela prend un temps exponentiel; comment puis-je résoudre ce problème plus efficacement?

Une solution de programmation dynamique fonctionnerait ici si le contenu en vitamines provenait d'un ensemble fini (par exemple, des entiers bornés). Tout d'abord, triez les fruits selon le prix croissant et dans le cas où deux fruits ou plus ont le même prix, triez-les en fonction de la teneur en vitamines (décroissant). Maintenant, définissez comme le nombre maximal de fruits dans une sous-liste, ne contenant que les derniers fruits (de la liste triée), ayant une teneur en vitamines d'au plus . et utilisation de la programmation dynamique vous offre une solution qui s'exécute dans$M[f, v]$$f$$v$$M[0, *] = 0$

$$M[f, v] = \begin{cases} \mathrm{max} \{M[f-1, v], 1 + M[f-1, V_f]\} & \text{if \(V_f <= v\)} \\ M[f-1, v] & \text{otherwise} \\ \end{cases}$$ $O(\text{number of fruit} \times \text{possible vitamin values})$ .