고유한 요소로 구성된 배열이 제공되는 문제를 해결합니다. 이제 우리의 임무는 모든 쌍이 균등하게 나눌 수 있는 부분 집합을 찾는 것입니다. 예를 들어 모든 큰 요소는 모든 작은 요소로 나눌 수 있습니다.
입력 :arr[] ={10, 5, 3, 15, 20}출력 :3설명 :가장 큰 부분집합은 10, 5, 20.10은 5의 배수, 20은 10의 배수입니다.입력 :arr[] ={18, 1, 3, 6, 13, 17}출력:4설명:가장 큰 부분 집합은 18, 1, 3, 6입니다. 부분 수열에서 3은 1,6의 3, 18의 6의 배수입니다.
이 문제에 대한 답을 찾기 위해 동적 프로그래밍을 적용하고 그 방법을 알아보겠습니다.
해결책을 찾기 위한 접근 방식
이 접근 방식에서는 배열을 오름차순으로 정렬합니다. 이제 끝에서 시작하여 배열을 실행합니다. 이제 i번째 요소가 가장 작은 가장 큰 부분 집합의 크기를 포함하는 dp 배열을 유지 관리합니다. 그런 다음 dp 배열에서 최대값을 반환합니다.
예
#include 네임스페이스 std;int maximumSubsetPair(int *a, int n){ int dp[n]; // i번째 인덱스부터 시작하여 가장 큰 부분집합을 저장할 것입니다. dp[n - 1] =1; // 마지막 요소가 가장 크므로 하위 집합 크기는 1입니다. int maximum =0; // ans for (int i =n - 2; i>=0; i--) { int maxi =0; // 최대 =0을 취합니다. for (int j =i + 1; j 출력
4
위 코드 설명
이 접근 방식에서는 이제 동적 프로그래밍을 사용하여 문제를 해결합니다. 먼저 배열을 정렬합니다. 이제 배열을 정렬하면서 이전의 가장 큰 하위 집합을 모두 저장할 배열 dp를 만들었습니다.
이제 우리는 배열의 끝에서 시작합니다. 먼저 현재 요소가 최소라고 가정하고 그 앞에 배수가 발생하면 다른 배수를 확인합니다. 우리는 역으로 여행하고 있으므로 이전에 그 요소를 만난 적이 있음을 의미합니다. 또한 이제 dp 배열 내부에 가장 큰 하위 집합 크기를 저장했습니다. 현재 요소의 dp에 이 요소를 추가하고 계속 진행합니다.
결론
이 자습서에서는 동적 프로그래밍을 사용하여 가장 큰 나눌 수 있는 쌍 하위 집합을 찾는 문제를 해결합니다. 우리는 또한 이 문제에 대한 C++ 프로그램과 이 문제를 해결하기 위한 완전한 접근 방식(Normal)을 배웠습니다. C, Java, python 및 기타 언어와 같은 다른 언어로 동일한 프로그램을 작성할 수 있습니다. 이 튜토리얼이 도움이 되기를 바랍니다.