Programme C++ pour trouver le plus grand sous-ensemble de nombres divisible

Résolvez le problème étant donné un tableau composé de différents éléments. Notre tâche est maintenant de trouver des sous-ensembles tels que chaque paire soit divisible, c'est-à-dire que chaque grand élément est divisible par chaque élément plus petit.

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.

Nous appliquerons la programmation dynamique pour trouver la réponse à cette question et nous verrons comment la mettre en œuvre.

Méthode pour trouver une solution

Dans cette méthode, nous trierons notre tableau par ordre croissant. Maintenant, nous parcourons le tableau en commençant par la fin du tableau. Nous maintenons maintenant un tableau dp contenant la taille du plus grand sous-ensemble avec le plus petit i-ème élément. Ensuite, nous renvoyons la valeur maximale dans le tableau dp.

Exemple

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

Sortie

4

Explication du code ci-dessus

Dans cette approche, nous utilisons maintenant la programmation dynamique pour résoudre le problème. Tout d’abord, nous trions maintenant le tableau. Lorsque nous trions maintenant le tableau, nous créons un tableau dp pour stocker tous les plus grands sous-ensembles précédents.

Maintenant, nous partons de la fin du tableau. Nous supposons d’abord que l’élément actuel est le plus petit et vérifions les autres multiples lorsque nous rencontrons le multiple précédent. Nous voyageons en sens inverse, ce qui signifie que nous avons déjà rencontré cet élément. Nous enregistrons désormais également leur taille maximale de sous-ensemble dans le tableau dp. Nous ajoutons cet élément au dp de l'élément actuel et c'est ainsi que nous procédons.

Conclusion

Dans ce tutoriel, nous avons résolu le problème de la recherche du sous-ensemble de paires maximum divisible à l'aide de la programmation dynamique. Nous avons également appris le programme C++ pour ce problème et la méthode complète (générique) pour le résoudre. Nous pouvons écrire le même programme dans d'autres langages tels que C, Java, Python et d'autres langages. Nous espérons que vous avez trouvé ce tutoriel utile.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!