เพื่อแก้ปัญหาที่เราได้รับอาร์เรย์ที่ประกอบด้วยสมาชิกที่ไม่ซ้ำกัน ตอนนี้ภารกิจของเราคือหา Subset ที่ทุกคู่หารลงตัวได้อย่างสม่ำเสมอ (Evenly Divisible) คือ สมาชิกที่ใหญ่กว่าหารด้วยสมาชิกที่เล็กกว่าลงตัว เช่น
Input : arr[] = {10, 5, 3, 15, 20} Output : 3 Explanation: Subset ใหญ่ที่สุดคือ 10, 5, 20. 10 หาร 5 ลงตัว และ 20 หาร 10 ลงตัว
Input : arr[] = {18, 1, 3, 6, 13, 17} Output : 4 Explanation: Subset ใหญ่ที่สุดคือ 18, 1, 3, 6, ใน subsequence นี้ 3 หาร 1 ลงตัว, 6 หาร 3 ลงตัว และ 18 หาร 6 ลงตัว
เราจะใช้ Dynamic Programming เพื่อหาคำตอบของปัญหานี้
วิธีการแก้ปัญหา
ในวิธีนี้ เราจะจัดเรียงอาร์เรย์ในลำดับน้อยไปมาก ตอนนี้เราวิ่งผ่านอาร์เรย์ เริ่มจากท้าย มา หน้า เราเก็บอาร์เรย์ dp ที่จะมีขนาดของ Subset ใหญ่ที่สุดที่สมาชิก i เป็นตัวเล็กที่สุด แล้วคืนค่าสูงสุดจากอาร์เรย์ dp
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
int largestSubsetPair(int *a, int n){
int dp[n];
dp[n - 1] = 1;
int largest = 0;
for (int i = n - 2; i >= 0; i--) {
int maxi = 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]);
dp[i] = 1 + maxi;
largest = max(largest, dp[i]);
}
return largest;
}
int main(){
int a[] = { 1, 3, 6, 13, 17, 18 };
int n = sizeof(a) / sizeof(int);
cout << largestSubsetPair(a, n) << "\n";
return 0;
}
ผลลัพธ์
4
คำอธิบายโค้ด
ในวิธีนี้ เราแก้ปัญหาด้วย Dynamic Programming ก่อนอื่น เราจัดเรียงอาร์เรย์ ตอนนี้เราจัดเรียงอาร์เรย์แล้ว เราสร้างอาร์เรย์ dp ที่จะเก็บขนาด Subset ใหญ่ที่สุดก่อนหน้า ตอนนี้เราเริ่มจากท้ายอาร์เรย์ เราสมมติว่าสมาชิกปัจจุบันเป็นค่าต่ำสุด และตรวจสอบพหุคูณอื่นๆ ข้างหน้า เนื่องจากเราเดินย้อนกลับ หมายความว่าเราเจอสมาชิกนั้นมาก่อน เรายังเก็บขนาด Subset ใหญ่ที่สุดของพวกเขาไว้ใน dp แล้ว เราเพิ่มสมาชิกนี้เข้าไปใน dp ของสมาชิกปัจจุบัน และนั่นคือวิธีที่เราดำเนินการ
สรุป
ในบทช่วยสอนนี้ เราแก้ปัญหาการหา Largest divisible pairs subset โดยใช้ Dynamic Programming เรายังได้เรียนรู้โปรแกรม C++ และวิธีแก้ปัญหา ซึ่งสามารถเขียนในภาษาอื่น เช่น C, Java, Python ได้ หวังว่าจะเป็นประโยชน์
