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 中，這就是我們的處理方式。

結論

在本教學中，我們解決了使用 Dynamic 來尋找最大可整對子集的問題程式設計。我們也學習了該問題的 C 程序以及解決該問題的完整方法（普通）。我們可以用其他語言像是C、java、python等語言來寫同樣的程式。我們希望本教學對您有所幫助。

以上是C++程式尋找最大可整除的數對子集的詳細內容。更多資訊請關注PHP中文網其他相關文章！