บทช่วยสอนนี้จะกล่าวถึงปัญหาที่เราได้รับอาร์เรย์ของจำนวนเต็มบวกที่แตกต่างกัน เราจำเป็นต้องหาชุดย่อยที่ใหญ่ที่สุดเพื่อให้องค์ประกอบที่ใหญ่กว่าทุกคู่ถูกหารด้วยองค์ประกอบที่เล็กกว่า ตัวอย่างเช่น −
Input: nums[ ] = { 1, 4, 2, 6, 7}
Output: 1 2 4
Explanation:
All Divisible subsets are: (1, 2, 4), (1, 2, 6), (1, 7), etc
We have 2 subsets of length 3 in which all the pairs satisfy the condition.
Input: nums[ ] = { 1, 2, 3, 6 }
Output: 6 2 1 แนวทางในการหาแนวทางแก้ไข
มีสองแนวทางที่แตกต่างกันที่เราจะอธิบายในบทช่วยสอนนี้
แนวทางง่ายๆ
ในแนวทางง่ายๆ เราสามารถใช้การเรียกซ้ำเพื่อแก้ปัญหานี้ได้ เราจะนำแต่ละองค์ประกอบและตรวจสอบว่าควรรวมไว้ในเซตย่อยหรือไม่ สมมติว่าเราเริ่มต้นด้วยองค์ประกอบแรก เราจะมีสองตัวเลือก ไม่ว่าจะรวมอยู่ในเซตย่อยหรือไม่สำหรับองค์ประกอบแรก มารวมองค์ประกอบแรกกัน จากนั้นสำหรับองค์ประกอบที่สองที่จะรวมอยู่ในเซตย่อย องค์ประกอบนั้นควรถูกหารด้วยหรือแบ่งองค์ประกอบในสตริงย่อย นั่นคือองค์ประกอบแรก นี่คือวิธีที่เราจะไปทั่วทั้งอาร์เรย์ ดังนั้นจะมี 2^n เส้นทางที่เป็นไปได้ที่จะสร้างความซับซ้อนของเวลาของ O(2^n) มาดูแนวทางที่เป็นไปได้ในการแก้ปัญหานี้กัน
แนวทางที่มีประสิทธิภาพ
แนวทางที่มีประสิทธิภาพสามารถนำมาใช้โดยใช้โปรแกรมแบบไดนามิกในปัญหานี้
-
จัดเรียงอาร์เรย์เพื่อให้องค์ประกอบด้านซ้ายหารด้วยองค์ประกอบที่ถูกต้อง เราต้องตรวจสอบการหาร 1 ครั้ง
-
เราจะใช้ลำดับที่ยาวที่สุดที่เพิ่มขึ้น นั่นคืออาร์เรย์ dp[ ] ของเรา เพื่อเก็บเซ็ตย่อยที่ใหญ่ที่สุดที่หารได้ของดัชนี till ith เราจะเริ่มต้นแต่ละดัชนีด้วยหนึ่งรายการเพราะทุกองค์ประกอบแบ่งตัวมันเอง
-
ตอนนี้เราจะวนซ้ำจากดัชนีที่ 2 และตรวจสอบแต่ละองค์ประกอบเพื่อหาชุดย่อยที่หารได้มากที่สุดที่ลงท้ายด้วยดัชนีปัจจุบัน ด้วยวิธีนี้ เราจะพบเซตย่อยสูงสุดสำหรับแต่ละดัชนี
-
ตอนนี้สำรวจผ่านอาร์เรย์ และสำหรับทุกองค์ประกอบ ให้ค้นหาตัวหารที่มีจำนวนที่หารได้มากที่สุด และเปลี่ยนค่าการนับที่หารได้ของดัชนีปัจจุบันเป็นจำนวนที่หารได้ขององค์ประกอบนั้น + 1
ตัวอย่าง
รหัส C++ สำหรับแนวทางข้างต้น
#include<bits/stdc++.h>
using namespace std;
int main(){
int nums[] = {1, 2, 3, 6};
int n = sizeof(nums)/sizeof(int);
// sorting the array to exclude one condition for division.
sort(nums, nums+n);
vector <int> prev_res(n, -1);
// vector to store divisors of all the elements
vector <int> dp(n, 1);
int max = 1;
for (int i=1; i<n; i++){ // Check if there's a divisor of ith element present at jth index.
for (int j=0; j<i; j++){
if (nums[i]%nums[j] == 0){
// check If adding that increases the number of elements in subsequence.
if (dp[i] < dp[j] + 1){
dp[i] = dp[j]+1;
prev_res[i] = j;
}
}
}
// finding index having a maximum number of subsets.
if(max<dp[i])
max = dp[i];
}
cout << "Largest divisible subset in the array: ";
// printing the maximum subset
int k = max;
while (k >= 0){
cout << nums[k] << " ";
k = prev_res[k];
}
return 0;
} ผลลัพธ์
Largest divisible subset in the array: 6 2 1
บทสรุป
ในบทช่วยสอนนี้ เราได้พูดถึงปัญหา:เราจำเป็นต้องค้นหาเซตย่อยที่หารได้มากที่สุดในอาร์เรย์ที่กำหนดโดยที่จำนวนเต็มในแต่ละคู่จะหารลงตัว เราได้พูดคุยถึงแนวทางจากการเรียกซ้ำซึ่งสร้างความซับซ้อนของเวลาแบบเอ็กซ์โพเนนเชียล ดังนั้นเราจึงพูดถึงโซลูชันการเขียนโปรแกรมแบบไดนามิก เรายังพูดถึงโปรแกรม C++ สำหรับปัญหานี้ ซึ่งเราสามารถทำได้ด้วยภาษาโปรแกรม เช่น C, Java, Python เป็นต้น เราหวังว่าคุณจะพบว่าบทช่วยสอนนี้มีประโยชน์
