La catena più lunga che può essere disposta

Question

Ho trovato questo problema da qualche parte in un concorso e non sono ancora riuscito a trovare una soluzione.

I numeri interi positivi. Devo trovare il sottoinsieme più lungo che tra ogni due elementi vicini uno divide l'altro.

Quello che sto facendo è: sto creando il grafico. Poi sto connettendo i nodi in cui i numeri si dividono l'un l'altro. Dopo di che sto usando DFS (un nodo può essere connesso con due nodi).

Ma non tutti i casi di test sono veri nel sistema. Devo ordinare l'array prima di utilizzare DFS? Forse c'è un algoritmo speciale (dinamico)?

In mancanza di casi di test:

N = 5 
1 1 3 7 13 

Il mio codice dà l'uscita 4. Ma se io arrange questo array come questo:

3 1 7 1 13 

L'uscita è 5 ed è la vera risposta.

Ho anche utilizzato il metodo ricorsivo. Ma ho bisogno di qualcosa più veloce.

Answer 1

Questo è il percorso più lungo, leggermente camuffato. Possiamo risolvere questo problema come percorso più lungo preparando un grafico in cui due vertici sono adiacenti se e solo se soddisfano una relazione di divisibilità. Vedi sotto la regola orizzontale per un puntatore alla risposta desiderata.

La riduzione è (approssimativamente), dato un grafo non orientato in cui vorremmo trovare il percorso più lungo, assegnare a ciascun vertice un numero primo distinto. Emetti questi numeri primi, insieme con, per ciascun lato, la semiprima che è il prodotto dei suoi endpoint. (Abbiamo anche bisogno di altri due numeri primi e dei loro prodotti 2 | V | con i numeri primi dei vertici per preservare l'obiettivo in modo additivo.)

Ad esempio, se abbiamo un grafico

*---* 
| /| 
|/| 
|/ | 
*---*, 

quindi possiamo etichettare

2---3 
| /| 
|/| 
|/ | 
5---7, 

e quindi l'ingresso è

2, 3, 5, 7, # vertices 
2*3, 2*5, 3*5, 3*7, 5*7, # edges 
11*2, 11*3, 11*5, 11*7, # sentinels at one end 
2*13, 3*13, 5*13, 7*13, # sentinels at the other end 

e (ad esempio) il percorso più lungo 2, 3, 5, 7 corrisponde alla sequenza più lunga 11*2, 2, 2*3, 3, 3*5, 5, 5*7, 7, 7*13 (e altre tre varianti che riguardano versal e swapping 11 e 13).

---

più lungo percorso è NP-difficile, così il commento di nhahtdh circa O (2^n poli (n)) - programma dinamico il tempo è di destra sui soldi - vedere questa domanda e la risposta accettata: Longest path in unweighted undirected graph.

Answer 2

Si dimentica di reinserire alcune variabili: used e kol. Inoltre DFS non ripristina used[i] alla fine per le chiamate successive.

Cercare di evitare variabili globali, rende il codice meno chiaro. Prova anche a ridurre l'ambito della variabile.

Codice può guardare qualcosa di simile:

void DFS(int (&used)[20], const int (&m)[20][20], int c, int& maxn, int k, int v) { 
    used[v] = 1; 
    k += 1; 
    if(k > maxn) 
     maxn = k; 
    for(int i = 0; i < c; ++i) { 
     if(!used[i] && m[v][i] == 1) { 
      DFS(used, m, c, maxn, k, i); 
     } 
    } 
    used[v] = 0; 
} 

e nel principale:

int m[20][20]; 
memset(m, 0, sizeof(m)); 

for(int i = 0; i < c; ++i) { 
    for(int j = i + 1; j < c; ++j) { 
     if((a[i] % a[j] == 0) || (a[j] % a[i] == 0)) { 
      m[i][j] = m[j][i] = 1; // Creating 2D array 
     } 
    } 
} 

int maxn = 0; 
for(int i = 0; i < c; ++i) { 
    int used[20]; 
    int k = 0; 
    memset(used, 0, sizeof(used)); 
    DFS(used, m, c, maxn, k, i); 
} 
std::cout << maxn << std::endl; 

Live Demo

codice può essere semplificata ancora di più (utilizzare vector, ...)