Program C++ untuk mencari subset nombor boleh bahagi terbesar

Selesaikan masalah yang diberi tatasusunan yang terdiri daripada elemen yang berbeza. Sekarang tugas kita adalah untuk mencari subset supaya setiap pasangan boleh dibahagikan, iaitu setiap elemen besar boleh dibahagikan dengan setiap elemen yang lebih kecil.

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.

Kami akan menggunakan pengaturcaraan dinamik untuk mencari jawapan kepada soalan ini dan kami akan melihat bagaimana untuk melaksanakannya.

Kaedah untuk mencari penyelesaian

Dalam kaedah ini kami akan menyusun tatasusunan kami dalam tertib menaik. Sekarang kita lelaran melalui tatasusunan bermula dari penghujung tatasusunan. Kini kami mengekalkan tatasusunan dp yang mengandungi saiz subset terbesar dengan elemen ke-i terkecil. Kemudian kita kembalikan nilai maksimum dalam tatasusunan dp.

Contoh

#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;
}

Output

4

Penjelasan kod di atas

#🎜🎜🎜🎜 kita akan menggunakan pendekatan dinamik ini sekarang menyelesaikan masalah. Mula-mula, kita sekarang menyusun tatasusunan. Apabila kita sekarang mengisih tatasusunan, kita mencipta dp tatasusunan untuk menyimpan semua subset terbesar sebelumnya.

Sekarang kita mulakan dari hujung tatasusunan. Kami mula-mula menganggap bahawa elemen semasa adalah yang terkecil dan semak gandaan lain apabila menghadapi gandaan sebelumnya. Kami melakukan perjalanan secara terbalik, jadi ini bermakna kami pernah menemui elemen itu sebelum ini. Kami kini juga menyimpan saiz subset maksimum mereka dalam tatasusunan dp. Kami menambah elemen ini pada dp elemen semasa dan begitulah cara kami melakukannya.

Kesimpulan

Dalam tutorial ini, kami menyelesaikan masalah mencari pasangan subset boleh bahagi maksimum menggunakan pengaturcaraan Dinamik. Kami juga mempelajari program C++ untuk masalah ini dan kaedah lengkap (generik) untuk menyelesaikannya. Kita boleh menulis program yang sama dalam bahasa lain seperti C, java, python dan bahasa lain. Kami harap anda mendapati tutorial ini membantu.

Atas ialah kandungan terperinci Program C++ untuk mencari subset nombor boleh bahagi terbesar. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!