C++ 程序查找最大可整除对子集
c++server side programmingprogramming
解决给定一个由不同元素组成的数组的问题。现在我们的任务是找到一个子集，使得每对都是均匀可整除的，即每个大元素都可以被每个较小的元素整除。
输入:arr[] = {10, 5, 3, 15, 20}
输出:3
解释:最大的子集是 10、5、20。
10 可以被 5 整除，20 可以被 10 整除。
输入:arr[] = {18, 1, 3, 6, 13, 17}
输出:4
解释:最大的子集是 18、1、3、6，
在子序列中，3 可以被 1 整除，
6 可以被 3 整除，18 可以被 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; // ans
for (int i = n - 2; i >= 0; i--) {
int maxi = 0; // 取 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]); // 如果 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++ 程序以及我们解决这个问题的完整方法(正常)。我们可以用其他语言(如 C、java、python 和其他语言)编写相同的程序。我们希望您觉得本教程有用。
