查找最大可分对子集的 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和其他语言。我们希望本教程对您有所帮助。