ในบทความนี้ เราจะเรียนรู้วิธีการแก้ปัญหาต่อไปนี้:
ข้อความปัญหา — กำหนดกิจกรรม n กิจกรรม พร้อมเวลาเริ่มต้นและเวลาสิ้นสุด ต้องเลือกจำนวนกิจกรรมสูงสุดที่คนเดียวสามารถทำได้ โดยเขาทำกิจกรรมได้ทีละอย่างในเวลาเดียวกัน
สัญลักษณ์ตัวแปร:
- N - จำนวนกิจกรรมทั้งหมด
- S - อาร์เรย์ที่มีเวลาเริ่มต้นของทุกกิจกรรม
- F - อาร์เรย์ที่มีเวลาสิ้นสุดของทุกกิจกรรม
มาเปลี่ยนดูโค้ดตัวอย่างด้านล่างนี้:
# วิธี Greedy (โลภ)
ตัวอย่างโค้ด
# หาจำนวนกิจกรรมสูงสุดที่คนเดียวทำได้
def Activities(s, f):
n = len(f)
print("The selected activities are:")
# กิจกรรมแรกจะถูกเลือกเสมอ
i = 0
print(i, end=" ")
# สำหรับกิจกรรมที่เหลือ
for j in range(n):
# หากเวลาเริ่มต้นมากกว่าหรือเท่ากับเวลาสิ้นสุดของกิจกรรมก่อนหน้า
if s[j] >= f[i]:
print(j, end=" ")
i = j
# โปรแกรมหลัก
s = [1, 2, 0, 3, 2, 4]
f = [2, 5, 4, 6, 8, 8]
Activities(s, f)
ผลลัพธ์
The selected activities are: 0 1
ตัวแปรทั้งหมดถูกประกาศในขอบเขตท้องถิ่น (local scope) และการอ้างอิงของมันแสดงในรูปภาพด้านบน
สรุป
ในบทความนี้ เราได้เรียนรู้วิธีการเขียนโปรแกรม Python สำหรับ Activity Selection Problem โดยใช้ Greedy Algorithm
