나누어질 수 있는 가장 큰 숫자 부분 집합을 찾는 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 배열의 최대값을 반환합니다.

Example

#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

위 코드에 대한 설명

이 접근 방식에서는 이제 동적 프로그래밍을 사용하여 문제를 해결합니다. 먼저 배열을 정렬합니다. 이제 배열을 정렬할 때 이전의 가장 큰 하위 집합을 모두 저장하기 위해 dp 배열을 만듭니다.

이제 배열의 끝부터 시작합니다. 먼저 현재 요소가 가장 작다고 가정하고 이전 배수를 만나면 다른 배수를 확인합니다. 우리는 역방향으로 여행하고 있습니다. 이는 이전에 해당 요소를 접한 적이 있음을 의미합니다. 이제 최대 하위 집합 크기도 dp 배열에 저장됩니다. 우리는 이 요소를 현재 요소의 dp에 추가하고 이것이 우리가 하는 방법입니다.

결론

이 튜토리얼에서는 동적 프로그래밍을 사용하여 최대 분할 가능한 쌍 부분 집합을 찾는 문제를 해결했습니다. 우리는 또한 이 문제에 대한 C++ 프로그램과 이를 해결하기 위한 완전한 방법(일반)을 배웠습니다. C, Java, Python 및 기타 언어와 같은 다른 언어로 동일한 프로그램을 작성할 수 있습니다. 이 튜토리얼이 도움이 되었기를 바랍니다.

위 내용은 나누어질 수 있는 가장 큰 숫자 부분 집합을 찾는 C++ 프로그램의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!