แก้โจทย์ปัญหาการทอนเงินด้วยขั้นตอนวิธีแบบละโมบ (Greedy Algorithm)

หนึ่งในโจทย์ปัญหาการเขียนโปรแกรมที่นิยม คือ การทอนเงินด้วยเหรียญหรือธนบัตรตามที่กำหนด โดยโจทย์ต้องการหาจำนวนเหรียญหรือธนบัตรที่น้อยที่สุดในการทอนเงินจำนวนที่กำหนด ซึ่งโจทย์นี้เป็นโจทย์ที่เราทุกคนคุ้นเคยและใช้ในชิวิตประจำวันบ่อยครั้ง

โดยบทความนี้อธิบายถึงการเขียนโปรแกรมคำนวณจำนวนเหรียญหรือธนบัตรที่น้อยที่สุดในการทอนเงิน โดยใช้วีธีการแบบละโมบ ¹² ด้วยตัวอย่างโปรแกรมในภาษา Golang

วีธีการแบบละโมบในการทอนเหรียญจำนวนน้อยที่สุด

การวิธีการคิดแบบละโมบเพื่อให้จำนวนเหรียญที่ต้องทอนน้อยที่สุด มีขั้นวนซ้ำจำนวนเหรียญที่เหลืออยู่ และใช้วีธีการ 1 อย่าง คือ เลือกทอนเหรียญที่มีมูลค่ามากที่สุดที่สามารถทอนในการทอนแต่ละครั้งที่ทำการวนซ้ำ

อธิบายวิธีการแบบละโมบของตัวอย่างการทอนเงินจำนวน 28 บาท ด้วยเหรียญ 1 บาท, 5 บาท และ 10 บาท

วิธีการวิธีการแบบละโมบของทอนเงินจำนวน 28 บาท ด้วยเหรียญ 1 บาท, 5 บาท และ 10 บาท สามารถอธิบายได้ดังนี้ (รูปที่ 1)

1. เริ่มต้นด้วยการทอนเหรียญ 10 บาท จำนวน 2 ครั้ง
2. เมื่อเหลือจำนวนเงินทอน 8 บาท ซึ่งน้อยกว่า 10 บาท เลือกเหรียญที่มีมาค่ามาที่สุดลำดับถัดไป คือ เหรียญ 5 บาท ทอนจำนวน 1 ครั้ง
3. จำนวนเงินทอนเหลือ 3 บาท จึงนำเหรียญ 1 บาท ทอนจำนวน 3 ครั้ง

เพราะฉะนั้นการทอนเงินจำนวน 28 บาท ต้องใช้เหรียญจำนวน 6 เหรียญ ซึ่งเป็นจำนวนที่น้อยที่สุด ประกอบด้วยเหรียญดังต่อไปนี้ เหรียญ 10 บาท จำนวน 2 เหรียญ, เหรียญ 5 บาท จำนวน 1 เหรียญ, และ เหรียญ 1 บาท จำนวน 3 เหรียญ

วิธีการตามตัวอย่างข้างต้นสามารถเขียนออกมาเป็นโฟลว์ชาร์ต (flowchart) ได้ตามรูปด้านล่าง

ตาม ตัวอย่าง flow chart สามารถเขียนโปรแกรมภาษา Golang ได้ดังนี้

func calculateChangeCoins(amount int) int {
	num_change_coins := 0
    //  loop until amount is zero
	for amount > 0 {
		switch {
		case amount >= 10:
			amount -= 10
		case amount >= 5:
			amount -= 5
		default:
			amount -= 1
		}
		num_change_coins += 1
	}
	return num_change_coins
}

สามารถปรับปรุงให้ดีขึ้นด้วยไม่ต้องใช้การวนซ้ำ (loop) ได้ตามตัวอย่างด้านล่าง

func calculateChangeCoins(amount int) int {
	return (amount / 10) + ((amount % 10) / 5) + (amount % 5)
}

ปัญหาของวีธีการแบบละโมบเป็นการทอนเหรียญให้น้อยที่สุดหรือไม่

การแก้ปัญหาการทอนเงินด้วยวิธีการแบบละโมบเป็นวิธีการที่ดีที่สุดแล้วหรือไม่ วิธีการนี้ไม่สามารถแก้ปัญหาในกรณีใดได้หรือไม่ เรามาลองเขียนโปรแกรมแก้โจทย์ปัญหาใน Leetcode ³ โดยใช้วิธีการแบบละโมบด้วยโปรแกรมที่ปรับปรุงให้สามารถรองรับเหรียญรูปแบบต่างๆ ตามตัวอย่างด้านล่าง

func calculateChangeCoins(coins []int, amount int) int {
	if len(coins) == 0 || amount < 0 {
		return -1
	}
	// sort the coins in descending order
	sort.Slice(coins, func(i, j int) bool {
		return coins[i] > coins[j]
	})

	// initialize variables
	num_change_coins := 0

	for _, current_coins := range coins {
        //  number of coins that can be used to change the amount
		num_change_coins += amount / current_coins
        //  remaining amount after changing the amount with the current coin
		amount %= current_coins

        //  if the amount is 0, return the number of coins used to change the amount
		if amount == 0 {
			return num_change_coins
		}
	}
	return -1
}

พบว่าไม่สามารถแก้ไขโจทย์ปัญหาในกรณีจำนวนเงิน 6,249 บาท และเหรียญที่มีค่าเป็น 186, 419, 83, และ 408 ได้ถูกต้อง โปรแกรมตามตัวอย่างด้านบนได้คำตอบ -1 (ไม่สามารถทอนเงิน ด้วยเหรียญที่กำหนดได้) แต่คำตอบที่ถูกต้อง คือ 20 เหรียญ เป็นจำนวนที่น้อยที่สุดในการทอนเงินจำนวน 6,249 บาท แสดงให้เห็นว่าวิธีการแก้ปัญหาด้วยวิธีการแบบละโมบไม่ได้เป็นวิธีการที่ได้คำตอบที่ถูกต้องเสมอไป

สรุปการเลือกใช้วิธีการแบบละโมบสำหรับการแก้ปัญหา

วิธีการแบบละโมบเป็นวิธีการที่ง่ายที่สุดในการแก้ปัญหา แต่ในบ้างครั้งไม่สามารถหาคำตอบที่ถูกต้องได้เสมอไป จึงควรพิจารณาวิธีการอื่นๆ เพื่อหาคำตอบที่ถูกต้องได้ เช่น การใช้วิธีการของฟังก์ชันแบบเรียกซ้ำ (recursive function) หรือ การเขียนโปรแกรมแบบไดนามิก (dynamic programming)