解决给定一个由不同元素组成的数组的问题。现在我们的任务是找到子集，使得每对都可以整除，即每个大元素都可以被每个较小元素整除。
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 来存储之前所有最大的子集。
立即学习“C++免费学习笔记（深入）”；
现在我们从数组的末尾开始。我们首先假设当前元素是最小的，并在遇到前面的倍数时检查其他倍数。我们是反向旅行，所以这意味着我们以前遇到过那个元素。我们现在还将它们的最大子集大小保存在 dp 数组中。我们将此元素添加到当前元素的 dp 中，这就是我们的处理方式。
结论
在本教程中，我们解决了使用 Dynamic 查找最大可整对子集的问题编程。我们还学习了该问题的 C++ 程序以及解决该问题的完整方法（普通）。我们可以用其他语言比如C、java、python等语言来编写同样的程序。我们希望本教程对您有所帮助。
