解决给定一个由不同元素组成的数组的问题。现在我们的任务是找到子集，使得每对都可以整除，即每个大元素都可以被每个较小元素整除。
Input : arr[] = {10, 5, 3, 15, 20}Output : 3Explanation: 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 : 4Explanation: 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 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等语言来编写同样的程序。我们希望本教程对您有所帮助。
以上就是C++程序寻找最大可整除的数对子集的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1445018.html
微信扫一扫 
支付宝扫一扫 
