配列内で最大の分割可能なサブセットを見つけるためのC++プログラム

このチュートリアルでは、異なる正の整数の配列が与えられる問題について説明します。すべてのペアについて、大きい要素が小さい要素で除算されるような最大のサブセットを見つける必要があります。たとえば、-

Input: nums[ ] = { 1, 4, 2, 6, 7}
Output: 1 2 4
Explanation:
All Divisible subsets are: (1, 2, 4), (1, 2, 6), (1, 7), etc
We have 2 subsets of length 3 in which all the pairs satisfy the condition.

Input: nums[ ] = { 1, 2, 3, 6 }
Output: 6 2 1

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

このチュートリアルで説明する2つの異なるアプローチがあります。

シンプルなアプローチ

簡単なアプローチでは、再帰を適用してこの問題を解決できます。各要素を取得して、サブセットに含める必要があるかどうかを確認します。最初の要素から始めたとしましょう。サブセットに含めるか、最初の要素に含めないかの2つのオプションがあります。最初の要素を含めましょう。次に、2番目の要素をサブセットに含めるには、サブストリング内の要素、つまり最初の要素で除算または分割する必要があります。これが、アレイ全体を移動する方法です。したがって、O（2 ^ n）の時間計算量を作成する2^nの可能なパスがあります。この問題を解決するための実行可能なアプローチを見てみましょう。

効率的なアプローチ

この問題で動的計画法を使用することにより、効率的なアプローチを適用できます。

• 配列を並べ替えて、左側の要素を正しい要素で割り切れるようにします。分割可能性を一度チェックする必要があります。

• 最長増加部分列、つまりdp []配列を使用して、i番目までのインデックスの最大の除算サブセットを格納します。すべての要素がそれ自体を分割するため、各インデックスを1で初期化します。

• 次に、2番目のインデックスから繰り返し、現在のインデックスで終わる最大の分割可能なサブセットについて各要素をチェックします。このようにして、各インデックスの最大サブセットを見つけます。

• 次に、配列をトラバースし、すべての要素について、除算可能な数が最大の除数を見つけます。そして、現在のインデックスの除算カウント値を、その要素の除算カウント+1に変更します。

例

上記のアプローチのC++コード

#include<bits/stdc++.h>
using namespace std;
int main(){
    int nums[] = {1, 2, 3, 6};
    int n = sizeof(nums)/sizeof(int);
    // sorting the array to exclude one condition for division.
    sort(nums, nums+n);
    vector <int> prev_res(n, -1);
    // vector to store divisors of all the elements
    vector <int> dp(n, 1);
    int max = 1;
    for (int i=1; i<n; i++){   // Check if there's a divisor of ith element present at jth index.
        for (int j=0; j<i; j++){
            if (nums[i]%nums[j] == 0){
            // check If adding that increases the number of elements in subsequence.
                if (dp[i] < dp[j] + 1){
                    dp[i] = dp[j]+1;
                    prev_res[i] = j;
                   
                }
            }
        }
   
        // finding index having a maximum number of subsets.
        if(max<dp[i])
            max = dp[i];
    }
    cout << "Largest divisible subset in the array: ";
    // printing the maximum subset
    int k = max;
    while (k >= 0){
        cout << nums[k] << " ";
        k = prev_res[k];
    }
    return 0;
}

出力

Largest divisible subset in the array: 6 2 1

結論

このチュートリアルでは、問題について説明しました。各ペアの整数が除算可能である、指定された配列内の最大の除算可能なサブセットを見つける必要があります。指数関数的な時間計算量を生み出す再帰からのアプローチについて説明したので、動的計画法ソリューションについて説明しました。また、C、Java、Pythonなどのプログラミング言語で実行できるこの問題のC++プログラムについても説明しました。このチュートリアルがお役に立てば幸いです。