查找最大可分对子集的 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]; // 它将存储从第 i 个索引开始的最大子集
    dp[n - 1] = 1; // 因为最后一个元素是最大的所以它的子集大小是 1
    int largest = 0; // 回答
    for (int i = n - 2; i >= 0; i--) {
        int maxi = 0; // 取最大值 = 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]); // 如果 a[j] 可被 a[i] 整除
                 //所以所有可被 a[j] 整除的元素也应该遵循

        dp[i] = 1 + maxi;
        largest = max(largest, dp[i]);
    }
    return largest;
}
int main(){
    int a[] = { 1, 3, 6, 13, 17, 18 }; // 给定数组
    int n = sizeof(a) / sizeof(int); // 我们数组的大小
    cout << largestSubsetPair(a, n) << "\n";
    return 0;
}

4

以上代码说明

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

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

结论

在本教程中，我们使用动态规划解决了一个问题，以找到最大的可分对子集。我们还学习了针对此问题的 C++ 程序以及解决此问题的完整方法(Normal)。我们可以用其他语言编写相同的程序，例如 C、java、python 和其他语言。我们希望本教程对您有所帮助。