C++ program to find the largest divisible subset of numbers

Solve the problem of being given an array consisting of different elements. Now our task is to find subsets such that every pair is divisible, i.e. every large element is divisible by every smaller element.

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.

We will apply dynamic programming to find the answer to this question and we will see how to implement it.

Method to find solution

In this method we will sort our array in ascending order. Now we iterate through the array starting from the end of the array. Now we maintain a dp array containing the size of the largest subset with the smallest i-th element. Then we return the maximum value in the dp array.

Example

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

Output

4

Explanation of the above code

In this approach, we now use dynamic programming to solve the problem. First, we now sort the array. When we now sort the array, we create an array dp to store all previous largest subsets.

Now we start from the end of the array. We first assume that the current element is the smallest and check other multiples when encountering the previous multiple. We're traveling in reverse, so that means we've encountered that element before. We now also save their maximum subset size in the dp array. We add this element to the dp of the current element and that's how we do it.

Conclusion

In this tutorial, we solved the problem of finding the maximum divisible pair subset using Dynamic programming. We also learned the C program for this problem and the complete method (general) to solve it. We can write the same program in other languages ​​such as C, java, python and other languages. We hope you found this tutorial helpful.

The above is the detailed content of C++ program to find the largest divisible subset of numbers. For more information, please follow other related articles on the PHP Chinese website!