แนวคิดแบบโลภ
เลือกขั้นตอนที่ดีที่สุดและไม่ย้อนกลับ
แนวคิดแบบโลภ เป็นบทเรียน Coding Interview Prep ฟรีบน CoddyKit นี่คือบทเรียนที่ 1 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน Coding Interview Prep และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส Coding Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน
ความหมายของอัลกอริทึมแบบละโมบ
อัลกอริทึมแบบละโมบสร้างคำตอบทีละขั้น โดยเลือกตัวเลือกที่ดูดีที่สุดในขณะนั้นเสมอ และไม่ย้อนกลับไปยกเลิกภายหลัง ⚡
เลือกขั้นตอนที่ดีที่สุด
ในทุกขณะให้ถามเพียงหนึ่งเรื่อง: ตัวเลือกใดช่วยได้มากที่สุดในระดับ เฉพาะหน้า? เลือกตัวเลือกนั้น แล้วไปยังการตัดสินใจถัดไป
ไม่ย้อนกลับ
แบบละโมบตัดสินใจแล้ว ไม่ย้อนการเลือก ต่างจากการย้อนรอย มันไม่สำรวจเส้นทางอื่น ซึ่งเป็นเหตุผลที่ทำให้เร็วมาก
เหตุใดอัลกอริทึมแบบละโมบจึงเร็ว
เพราะตัดสินใจครั้งเดียวต่อขั้น แบบละโมบมักทำงานใน O(n) หรือ O(n log n) หลังการเรียงลำดับ ความเร็วนี้คือจุดเด่นที่สุดในการแข่งขัน
นิสัยเริ่มด้วยการเรียงลำดับ
วิธีแก้ปัญหาแบบละโมบส่วนใหญ่เริ่มจากการ เรียงลำดับ รายการ ลำดับจะเผยให้เห็นว่าองค์ประกอบใดเป็นตัวเลือกที่ดีที่สุดอย่างชัดเจนในแต่ละขั้น
items.sort(key=lambda x: x.cost)คุณสมบัติการเลือกแบบละโมบ
แบบละโมบใช้ได้ก็ต่อเมื่อการเลือกที่ดีที่สุดในระดับ เฉพาะหน้า เป็นส่วนหนึ่งของคำตอบที่ดีที่สุดโดยรวมบางคำตอบ นี่คือคุณสมบัติการเลือกแบบละโมบ
ไม่ถูกต้องเสมอไป
การคว้าขั้นตอนที่ดีที่สุดตอนนี้ยังอาจ ล้มเหลว โดยรวม การทอนเงินด้วยเหรียญมูลค่าแปลกเป็นกรณีคลาสสิกที่แบบละโมบให้ยอดรวมผิด
พิสูจน์หรือทดสอบ
ก่อนเชื่อถือแบบละโมบ ให้ ให้เหตุผลรองรับ ด้วยข้อโต้แย้งแบบสลับ หรือทดสอบอย่างหนักกับอินพุตขนาดเล็กโดยเทียบกับการค้นหาแบบครบทุกกรณี
ข้อโต้แย้งแบบสลับ
การพิสูจน์แบบ สลับ จะแทนที่ตัวเลือกของแบบละโมบเข้าไปในคำตอบที่ดีที่สุด และแสดงว่าผลลัพธ์ไม่แย่ลง หากเป็นจริง แบบละโมบก็ปลอดภัย
ลูปแบบละโมบขนาดเล็ก
นี่คือ โครงร่าง ของอัลกอริทึมแบบละโมบเกือบทุกแบบ: เรียงลำดับ แล้วไล่ผ่านครั้งเดียว โดยเลือกสิ่งที่ตรงตามกฎ
items.sort()
for x in items:
if fits(x):
take(x)เมื่อใดควรเลือกแบบละโมบ
ลองใช้แบบละโมบเมื่อมี ลำดับ ที่ชัดเจนสำหรับจัดอันดับตัวเลือก และกฎหนึ่งยังคงให้ผลดีที่สุด หากตัวเลือกเกี่ยวข้องกันอย่างยุ่งยาก ให้หันไปใช้ DP แทน
ตรวจสอบอย่างรวดเร็ว
กำลังตัดสินใจว่าวิธีแบบละโมบน่าเชื่อถือหรือไม่
สรุป
แบบละโมบเลือก ขั้นตอนเฉพาะหน้าที่ดีที่สุด และไม่ย้อนกลับ โดยมักเรียงลำดับก่อน วิธีนี้เร็ว แต่จะถูกต้องก็ต่อเมื่อพิสูจน์ได้ว่าการเลือกแบบละโมบใช้ได้ 🚀
คำถามที่พบบ่อย
บทเรียน “แนวคิดแบบโลภ” ฟรีหรือไม่
ใช่ — ข้อความเต็มของ “แนวคิดแบบโลภ” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส Coding Interview Prep ให้อัปเกรดเป็น CoddyKit PRO คอร์ส Coding Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน
คุณจะเรียนรู้อะไรในบทเรียน “แนวคิดแบบโลภ”
เลือกขั้นตอนที่ดีที่สุดและไม่ย้อนกลับ คุณปฏิบัติ Coding Interview Prep ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน
คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน Coding Interview Prep หรือไม่
ไม่จำเป็นต้องมีประสบการณ์มาก่อน Coding Interview Prep บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 1 จากทั้งหมด 4 บทเรียน
บทเรียน “แนวคิดแบบโลภ” ใช้เวลานานแค่ไหน
บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย
ฉันเขียนและรันโค้ดในบทเรียน Coding Interview Prep นี้ได้ไหม
ได้ บทเรียน Coding Interview Prep ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ
บทเรียนทั้งหมดในหลักสูตรนี้
- แนวคิดแบบโลภ
- การเลือกกิจกรรมตามเวลาสิ้นสุดที่เร็วที่สุด
- กระเป๋าแบบแบ่งส่วนตามอัตราส่วน
- สังเกตว่าเมื่อใดวิธีโลภใช้ไม่ได้