บทช่วยสอนนี้จะอภิบัติปัญหาที่เราได้รับอาร์เรย์ของจำนวนเต็มบวกที่ไม่ซ้ำกัน เราต้องหา Subset ใหญ่ที่สุด ที่สำหรับทุกคู่ สมาชิกที่ใหญ่กว่าหารด้วยสมาชิกที่เล็กกว่าลงตัว เช่น
Input: nums[ ] = { 1, 4, 2, 6, 7} Output: 1 2 4 Explanation: Subset ที่หารลงตัวได้หมดคือ: (1, 2, 4), (1, 2, 6), (1, 7) ฯลฯ มี 2 subset ขนาด 3 ที่เงื่อนไขเป็นจริง
Input: nums[ ] = { 1, 2, 3, 6 } Output: 6 2 1
วิธีการแก้ปัญหา
มีสองวิธีที่แตกต่างกันที่เราจะอธิบายในบทช่วยสอนนี้
วิธีง่าย (Simple Approach)
ในวิธีง่าย เราสามารถใช้ Recursion แก้ปัญหา เราจะพิจารณาแต่ละสมาชิกว่าควรรวมใน Subset หรือไม่ สมมติเริ่มจากสมาชิกแรก เรามี 2 ทางเลือก: รวมหรือไม่รวม ถ้ารวมสมาชิกแรก สำหรับสมาชิกที่สองให้รวม ต้องหารลงตัวหรือถูกหารด้วยสมาชิกใน Substring คือสมาชิกแรก เราจะดำเนินต่อไปจนจบอาร์เรย์ จะมี 2^n เส้นทาง สร้าง Time Complexity O(2^n) มาดูวิธีที่เป็นไปได้มากกว่า
วิธีมีประสิทธิภาพ (Efficient Approach)
วิธีที่มีประสิทธิภาพสามารถใช้ Dynamic Programming ได้
- จัดเรียงอาร์เรย์เพื่อให้สมาชิกซ้ายหารด้วยสมาชิกขวาลงตัว ต้องเช็ค divisibility แค่ครั้งเดียว
- เราจะใช้ Longest Increasing Subsequence (LIS) คืออาร์เรย์ dp[] เพื่อเก็บ Largest Divisible Subset จนถึงดัชนี i เริ่มต้นแต่ละดัชนีเป็น 1 เพราะทุกตัวหารตัวเองลงตัว
- วนลูปจากดัชนีที่ 2 ตรวจสอบแต่ละสมาชิกหา Maximum Divisible Subset ที่ลงท้ายด้วยดัชนีปัจจุบัน
- วนลูปผ่านอาร์เรย์ สำหรับแต่ละสมาชิก หาตัวหารที่มี Divisible Count มากที่สุด แล้วเปลี่ยนค่า Divisible Count ของดัชนีปัจจุบันเป็นค่านั้น + 1
ตัวอย่าง
โค้ด C++ สำหรับวิธีการข้างต้น
#include<bits/stdc++.h>
using namespace std;
int main(){
int nums[] = {1, 2, 3, 6};
int n = sizeof(nums)/sizeof(int);
sort(nums, nums+n);
vector <int> prev_res(n, -1);
vector <int> dp(n, 1);
int max = 1;
for (int i=1; i<n; i++){
for (int j=0; j<i; j++){
if (nums[i]%nums[j] == 0){
if (dp[i] < dp[j] + 1){
dp[i] = dp[j]+1;
prev_res[i] = j;
}
}
}
if(max < dp[i]) max = dp[i];
}
cout << "Largest divisible subset in the array: ";
int k = max;
while (k >= 0){
cout << nums[k] << " ";
k = prev_res[k];
}
return 0;
}
ผลลัพธ์
Largest divisible subset in the array: 6 2 1
สรุป
ในบทช่วยสอนนี้ เราอภิบัติปัญหา: ต้องหา Largest Divisible Subset ในอาร์เรย์ที่กำหนด ซึ่งจำนวนเต็มในแต่ละคู่หารลงตัว เราอภิบัติวิธีจาก Recursion ที่สร้าง Complexity แบบ Exponential จึงอภิบัติวิธี Dynamic Programming เรายังอภิบัติโปรแกรม C++ สำหรับปัญหานี้ ซึ่งสามารถทำได้กับภาษาอื่น เช่น C, Java, Python ฯลฯ หวังว่าจะเป็นประโยชน์
