数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究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中，这就是我们继续进行的方式。
结论
在本教程中，我们解决了一个问题，使用动态规划查找最大可整除对子集。我们还学习了此问题的C++程序以及解决此问题的完整方法（常规）。我们可以用其他语言（如C、Java、Python等）编写相同的程序。我们希望您觉得本教程有帮助。
更新于: 2021年11月25日
156 次浏览
广告