Trouvez d'une longueur de séquence maximale satisfaisant simultanément deux contraintes d'ordre

Question

Nous sommes donné un ensemble $ F = \ {F-1, f_2, F_3, ..., f_n \} $ de $ N Fruits $. Chaque fruit a prix $ P_i $ et la teneur en vitamine $ v_i $; nous fruits associés $ f_i $ avec la paire ordonnée $ (P_i, v_i) $. Maintenant, nous devons organiser ces fruits de telle sorte que la liste triée contient les prix en ordre croissant et contenu vitamine dans l'ordre décroissant.

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

Si nous arrangeons la liste de telle sorte que tous les prix sont en ordre croissant et contenu vitamine dans l'ordre décroissant, alors 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)] $

A partir de la liste ci-dessus, je veux choisir la liste de la taille maximale. Si plus d'une liste a une taille maximale, il faut choisir la liste de la taille maximale dont la somme des prix est moins. 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 à cette instance est par exemple $ [(13100), (43,90), (78,65), (87,11), (99,10)] $.

Jusqu'à présent, c'est ce que je fais:

1. Trier la liste initiale dans l'ordre croissant de prix;
2. Trouver toutes les séquences de la liste triée;
3. Vérifiez si la séquence est valide et comparer toutes les séquences valides.

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

Answer 1

Une solution de programmation dynamique fonctionnerait ici, si le contenu en vitamines proviennent d'un ensemble fini (par exemple, des entiers bornés). Tout d'abord, trier les fruits sur le prix croissant et dans les cas étaient deux ou plus de fruits ont le même prix, les trier sur le contenu de la vitamine (descendante). Maintenant, définir M $ [f, v] $ pour le nombre de maximum de fruits dans une sous-liste, contenant seulement le dernier $ f $ fruits (de la liste triée), ayant une teneur en vitamine d'au plus $ v $. M $ [0, *] = 0 $ et $$ M [f, v] = \ begin {cas}  \ Mathrm {max} \ {M [f 1, v], 1 + M [f-1, v_F] \ &} \ texte {if \ (v_F <= v \) \\}  M [f-1, v] & \ texte {} sinon \\ \ end {cas} $$ En utilisant la programmation dynamique vous donne une solution qui fonctionne en $ O (\ texte {nombre de fruits} \ texte de fois {valeurs possibles de vitamine}) $.