Trova sottosequenza di lunghezza massima contemporaneamente soddisfare due vincoli di ordinazione

Question

viene fornita una serie $ F = \ {f_1, F_2, F_3, ..., f_N \} $ di $ N $ Frutta. Ogni frutto ha il prezzo $ p_i $ e contenuto di vitamina $ V_i $; abbiamo frutto associato $ $ f_i con la coppia ordinata $ (p_i, V_i) $. Ora dobbiamo organizzare questi frutti in modo tale che l'elenco ordinato contiene prezzi in ordine crescente e vitamine contenuti in ordine decrescente.

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

Se noi organizziamo la lista in modo tale che tutti i prezzi sono in ordine ascendente e vitamine contenuti in ordine decrescente, quindi le liste valide sono le seguenti:

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

Dagli elenchi di cui sopra, voglio scegliere l'elenco delle dimensione massima. Se più di una lista ha dimensione massima, dovremmo scegliere la lista delle dimensione massima la cui somma dei prezzi è meno. La lista che dovrebbe essere scelto nell'esempio di cui sopra è di $ \ {(5, 11), (7, 9), (10, 2) \} $.

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

La risposta a questo esempio istanza è $ [(13.100), (43,90), (78,65), (87,11), (99,10)] $.

Fino ad ora, questo è quello che ho fatto:

1. Ordinare l'elenco originale in ordine crescente di prezzo;
2. Trova tutte le sottosequenze della lista ordinata;
3. Verificare se la sottosequenza è valida, e confrontare tutte le sottosequenze validi.

Tuttavia, questo richiede tempo esponenziale; come posso risolvere questo problema in modo più efficiente?

Answer 1

Una soluzione di programmazione dinamica potrebbe funzionare qui, se il contenuto di vitamine provengono da un insieme finito (per esempio, gli interi delimitate). In primo luogo, ordinare i frutti su ascendente prezzo e nei casi erano due o più frutti hanno lo stesso prezzo, ordinare loro sul contenuto di vitamine (discendente). Ora, definire $ M [f, v] $ per essere il numero massimo di frutti in un elenco secondario, che contiene solo l'ultimo $ f $ frutti (della lista ordinata), con un contenuto di vitamina al massimo di $ v $. $ M [0, *] = 0 $ e $$ M [f, v] = \ begin {casi} \ Mathrm {max} \ {M [F-1, v], 1 + M [F-1, V_f] \} e \ text {if \ (V_f <= v \)} \\ & \ Text {altrimenti} M [, v f-1] \\ \ end {casi} $$ Utilizzando programmazione dinamica ti dà una soluzione che viene eseguito in $ O (\ text {numero di frutti} \ times \ text {possibili valori di vitamina}) $.