資料結構
網路
關係資料庫管理系統
作業系統
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 次瀏覽
廣告