C++程序寻找最大可整除的数对子集

解决给定一个由不同元素组成的数组的问题。现在我们的任务是找到子集，使得每对都可以整除，即每个大元素都可以被每个较小元素整除。

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.

我们将应用动态规划来找到这个问题的答案，我们将看看如何实现。

寻找解决方案的方法

在这种方法中，我们将按升序对我们的数组进行排序。现在我们从数组的末尾开始遍历数组。现在我们维护一个 dp 数组，其中包含第 i 个元素最小的最大子集的大小。然后我们返回 dp 数组中的最大值。

示例

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

输出

4

上述代码的解释

在这种方法中，我们现在使用动态规划来解决问题。首先，我们现在对数组进行排序。当我们现在对数组进行排序时，我们创建了一个数组 dp 来存储之前所有最大的子集。

现在我们从数组的末尾开始。我们首先假设当前元素是最小的，并在遇到前面的倍数时检查其他倍数。我们是反向旅行，所以这意味着我们以前遇到过那个元素。我们现在还将它们的最大子集大小保存在 dp 数组中。我们将此元素添加到当前元素的 dp 中，这就是我们的处理方式。

结论

在本教程中，我们解决了使用 Dynamic 查找最大可整对子集的问题编程。我们还学习了该问题的 C++ 程序以及解决该问题的完整方法（普通）。我们可以用其他语言比如C、java、python等语言来编写同样的程序。我们希望本教程对您有所帮助。

以上是C++程序寻找最大可整除的数对子集的详细内容。更多信息请关注PHP中文网其他相关文章！