Finden Sie die Unterbringung der maximalen Länge gleichzeitig zwei Bestellbeschränkungen

Question

Wir erhalten einen Satz $ f = {f_1, f_2, f_3,…, f_n } $ von $ n $ fruits. Jedes Frucht hat Preis $ p_i $ und Vitamin -Inhalt $ v_i $; Wir haben Fruit $ f_i $ mit dem bestellten Paar $ (p_i, v_i) $ verbunden. Jetzt müssen wir diese Früchte so anordnen, dass die sortierte Liste Preise in aufsteigender Reihenfolge und Vitamingehalt in absteigender Reihenfolge enthält.

Beispiel 1: $ N = 4 $ und $ f = {(2, 8), (5, 11), (7, 9), (10, 2) } $.

Wenn wir die Liste so ordnen, dass der gesamte Preis in der Reihenfolge und in der Vitamin -Inhalt in absteigender Reihenfolge liegt, sind die gültigen Listen Folgendes:

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

In den oben genannten Listen möchte ich die Liste der maximalen Größe auswählen. Wenn mehr als eine Liste eine maximale Größe aufweist, sollten wir die Liste der maximalen Größe auswählen, deren Preissumme am geringsten ist. Die Liste, die im obigen Beispiel ausgewählt werden sollte, lautet $ {(5, 11), (7, 9), (10, 2) } $.

Beispiel 2: $ N = 10 $ und $$ f = {(99,10), (12,23), (34,4), (10,5), (87,11), (19,10), (90,18), (43,90), (13.100), (78.65) } $$

Die Antwort auf diese Beispielinstanz lautet $ [(13.100), (43.90), (78.65), (87,11), (99,10)] $.

Bis jetzt habe ich das getan:

1. Sortieren Sie die ursprüngliche Liste in aufsteigender Reihenfolge des Preises;
2. Finden Sie alle Untersequenzen der sortierten Liste;
3. Überprüfen Sie, ob die Subsequenz gültig ist, und vergleichen Sie alle gültigen Subsequenzen.

Dies braucht jedoch eine exponentielle Zeit; Wie kann ich dieses Problem effizienter lösen?

Answer 1

Eine dynamische Programmierlösung würde hier funktionieren, wenn der Vitamingehalt aus einem endlichen Satz (zum Beispiel begrenzte ganze Zahlen) stammt. Sortieren Sie zunächst die Früchte zum Aufsteigen des Preises und in den Fällen haben zwei oder mehr Früchte den gleichen Preis und sortieren Sie sie auf Vitamingehalt (absteigend). Definieren Sie nun $ M [F, v] $ als die maximale Anzahl von Früchten in einem Sublisten, der nur die letzten $ f $ fruits (der sortierten Liste) enthält und einen Vitamingehalt von höchstens $ v $ hat. $ M [0, *] = 0 $ und $$ 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 {sonst} end {case Läuft in $ o ( text {Anzahl der Obst} Times text {mögliche Vitaminwerte}) $.