最大の分割可能なペアサブセットを見つけるための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.

この問題に対する答えを見つけるために動的計画法を適用し、その方法を見ていきます。

解決策を見つけるためのアプローチ

このアプローチでは、配列を昇順で並べ替えます。ここで、最後から始めて、配列を実行します。ここで、i番目の要素が最小である最大のサブセットのサイズを含むdp配列を維持します。次に、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、その他の言語などの他の言語で作成できます。このチュートリアルがお役に立てば幸いです。