Längste Kette, die arrangiert werden kann

Question

Ich habe dieses Problem irgendwo in einem Wettbewerb gefunden und konnte noch keine Lösung finden.

Ich habe die positiven ganzen Zahlen. Ich muss die längste Teilmenge finden, die unter je zwei Nachbarelemente eines anderen teilt.

Was ich mache ist: Ich erstelle das Diagramm. Dann verbinde ich Knoten, in denen Zahlen sich gegenseitig teilen. Danach benutze ich DFS (ein Knoten kann mit zwei Knoten verbunden sein).

Aber nicht alle Testfälle sind im System wahr. Muss ich das Array vor der Verwendung von DFS sortieren? Vielleicht gibt es einen speziellen (dynamischen) Algorithmus?

Failing Testfälle:

N = 5 
1 1 3 7 13 

Mein Code gibt den Ausgang 4. Aber wenn ich dieses Array wie folgt arrange:

3 1 7 1 13 

Der Ausgang ist 5 und es ist die wahre Antwort.

Ich verwendete auch rekursive Methode. Aber ich brauche etwas schneller.

Answer 1

Dies ist der längste Weg, leicht getarnt. Wir können dieses Problem als längsten Pfad lösen, indem wir einen Graphen erstellen, in dem zwei Vertices genau dann benachbart sind, wenn sie eine Teilbarkeitsbeziehung erfüllen. Siehe unten die horizontale Regel für einen Zeiger auf die beabsichtigte Antwort.

Die Reduktion ist (grob gesagt), bei einem ungerichteten Graph, in dem wir den längsten einfachen Pfad finden möchten, jedem Knoten eine eigene Primzahl zuweisen. Senden Sie diese Primzahlen zusammen mit, für jede Kante, den Semiprime, der das Produkt seiner Endpunkte ist. (Wir brauchen auch zwei weitere Primzahlen und ihre 2 | V | -Produkte mit den Eckpunkten, um das Ziel additiv zu erhalten.

)

Zum Beispiel, wenn wir einen Graphen

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

dann haben wir

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

beschriften und dann die Eingabe

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 

und (zum Beispiel) der längste Weg 2, 3, 5, 7 entspricht der längsten Sequenz 11*2, 2, 2*3, 3, 3*5, 5, 5*7, 7, 7*13 (und drei weiteren Varianten mit re Versal und Swapping 11 und 13).

---

Längster Weg ist NP-hart, so Kommentar des nhahtdh über einen O (2^n Poly (n)) - Zeit dynamisches Programm ist direkt auf dem Geld - siehe diese Frage und die akzeptierte Antwort: Longest path in unweighted undirected graph.

Answer 2

Sie vergessen, einige Variablen zu reintegrieren: used und kol. Darüber hinaus DFS nicht used[i] am Ende für nächste Anrufe wiederherstellen.

Versuchen Sie, globale Variablen zu vermeiden, es macht den Code weniger klar. Versuchen Sie auch, den Umfang der Variablen zu reduzieren.

-Code auf etwas aussehen kann:

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; 
} 

und in Haupt:

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

Kodex vereinfacht werden kann noch mehr (verwenden vector, ...)