Để giải quyết một vấn đề trong đó chúng ta được cung cấp một mảng bao gồm các phần tử riêng biệt. Bây giờ nhiệm vụ của chúng ta là tìm tập hợp con sao cho mọi cặp đều có thể chia đều, tức là mọi phần tử lớn đều chia hết cho mọi phần tử nhỏ hơn, chẳng hạn.
Input:arr [] ={10, 5, 3, 15, 20} Output:3 Phép tính:Tập con lớn nhất là 10, 5, 20.10 chia hết cho 5 và 20 chia hết cho 10.Input:arr [] ={18, 1, 3, 6, 13, 17} Kết quả:4 Phép tính:Tập hợp con lớn nhất là 18, 1, 3, 6, Trong dãy con, 3 chia hết cho 1,6 cho 3 và 18 cho 6.
Chúng tôi sẽ áp dụng lập trình động để tìm câu trả lời cho vấn đề này và chúng tôi sẽ xem cách thực hiện.
Phương pháp tiếp cận để tìm giải pháp
Trong cách tiếp cận này, chúng ta sẽ sắp xếp mảng của mình theo thứ tự tăng dần. Bây giờ chúng ta chạy qua mảng, bắt đầu cho phần cuối. Bây giờ chúng ta duy trì một mảng dp sẽ chứa kích thước của tập con lớn nhất trong đó phần tử thứ i là nhỏ nhất. Sau đó, chúng tôi trả về giá trị lớn nhất từ mảng dp của chúng tôi.
Ví dụ
#include using namespace std; int largeSubsetPair (int * a, int n) {int dp [n]; // nó sẽ lưu trữ tập con lớn nhất bắt đầu từ chỉ số thứ i dp [n - 1] =1; // vì phần tử cuối cùng là phần tử lớn nhất nên kích thước tập con của nó là 1 int lớn nhất =0; // ans for (int i =n - 2; i> =0; i--) {int maxi =0; // lấy max =0; for (int j =i + 1; j Đầu ra
4
Giải thích về Quy tắc trên
Trong cách tiếp cận này, chúng tôi giải quyết vấn đề bằng cách sử dụng lập trình động ngay bây giờ. Đầu tiên, chúng tôi sắp xếp mảng của chúng tôi bây giờ. Khi chúng tôi sắp xếp mảng của mình bây giờ, chúng tôi đã tạo một mảng dp sẽ lưu trữ tất cả các tập con lớn nhất trước đó.
Bây giờ chúng ta bắt đầu từ cuối mảng của chúng ta trong điều này. Trước tiên, chúng tôi giả định rằng phần tử hiện tại của chúng tôi là tối thiểu và kiểm tra các bội số khác ngay bây giờ khi chúng tôi gặp một bội số phía trước nó. Chúng ta đang du hành ngược lại, vậy có nghĩa là chúng ta đã gặp phải yếu tố đó trước đó. Chúng tôi cũng đã lưu kích thước tập hợp con lớn nhất của chúng bên trong mảng dp của chúng tôi ngay bây giờ. Chúng tôi thêm phần tử này vào dp của phần tử hiện tại của chúng tôi và đó là cách chúng tôi tiến hành.
Kết luận
Trong hướng dẫn này, chúng tôi giải quyết một vấn đề để tìm tập hợp con các cặp chia lớn nhất bằng cách sử dụng Lập trình động. Chúng tôi cũng đã học chương trình C ++ cho vấn đề này và cách tiếp cận hoàn chỉnh (Bình thường) mà chúng tôi đã giải quyết vấn đề này. Chúng ta có thể viết cùng một chương trình bằng các ngôn ngữ khác như C, java, python và các ngôn ngữ khác. Chúng tôi hy vọng bạn thấy hướng dẫn này hữu ích.