割り切れる数値の最大の部分集合を見つけるための 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 などの他の言語で書くことができます。このチュートリアルがお役に立てば幸いです。

以上が割り切れる数値の最大の部分集合を見つけるための C++ プログラムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。