C++-Programm zum Finden der größten teilbaren Teilmenge von Zahlen

Lösen Sie das Problem anhand eines Arrays, das aus verschiedenen Elementen besteht. Unsere Aufgabe besteht nun darin, Teilmengen zu finden, bei denen jedes Paar teilbar ist, d. h. jedes große Element ist durch jedes kleinere Element teilbar.

Input : arr[] = {10, 5, 3, 15, 20}
Output : 3
Explanation: The largest subset is 10, 5, 20.
10 is divisible by 5, and 20 is divisible by 10.

Input : arr[] = {18, 1, 3, 6, 13, 17}
Output : 4
Explanation: The largest subset is 18, 1, 3, 6,
In the subsequence, 3 is divisible by 1,
6 by 3 and 18 by 6.

Wir werden dynamische Programmierung anwenden, um die Antwort auf diese Frage zu finden, und wir werden sehen, wie wir sie umsetzen können.

Methode zur Lösungsfindung

In dieser Methode sortieren wir unser Array in aufsteigender Reihenfolge. Jetzt durchlaufen wir das Array, beginnend am Ende des Arrays. Jetzt verwalten wir ein dp-Array, das die Größe der größten Teilmenge mit dem kleinsten i-ten Element enthält. Dann geben wir den Maximalwert im dp-Array zurück.

Beispiel

#include <bits/stdc++.h>
using namespace std;
int largestSubsetPair(int *a, int n){
    int dp[n]; // it is going to store the largest subset starting from ith index
    dp[n - 1] = 1; // as last element is the largest so its subset size is 1
    int largest = 0; // ans
    for (int i = n - 2; i >= 0; i--) {
        int maxi = 0; // taking max = 0;
        for (int j = i + 1; j < n; j++)
            if (a[j] % a[i] == 0 || a[i] % a[j] == 0)
                maxi = max(maxi, dp[j]); // if a[j] is divisible by a[i]
                 //so all the elements divisible by a[j] should also follow

        dp[i] = 1 + maxi;
        largest = max(largest, dp[i]);
    }
    return largest;
}
int main(){
    int a[] = { 1, 3, 6, 13, 17, 18 }; // given array
    int n = sizeof(a) / sizeof(int); // size of our array
    cout << largestSubsetPair(a, n) << "\n";
    return 0;
}

Ausgabe

4

Erklärung des obigen Codes

In diesem Ansatz verwenden wir nun dynamische Programmierung, um das Problem zu lösen. Zuerst sortieren wir nun das Array. Wenn wir nun das Array sortieren, erstellen wir ein Array dp, um alle vorherigen größten Teilmengen zu speichern.

Jetzt beginnen wir am Ende der Reihe. Wir gehen zunächst davon aus, dass das aktuelle Element das kleinste ist, und prüfen andere Vielfache, wenn wir auf das vorherige Vielfache stoßen. Wir reisen rückwärts, das heißt, wir sind diesem Element schon einmal begegnet. Wir speichern jetzt auch ihre maximale Teilmengengröße im dp-Array. Wir fügen dieses Element zum dp des aktuellen Elements hinzu und so machen wir es.

Fazit

In diesem Tutorial haben wir das Problem gelöst, die maximal teilbare Paarteilmenge mithilfe der dynamischen Programmierung zu finden. Wir haben auch das C++-Programm für dieses Problem und die vollständige (generische) Methode zu seiner Lösung gelernt. Wir können das gleiche Programm in anderen Sprachen wie C, Java, Python und anderen schreiben. Wir hoffen, dass Sie dieses Tutorial hilfreich fanden.

Das obige ist der detaillierte Inhalt vonC++-Programm zum Finden der größten teilbaren Teilmenge von Zahlen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!