Back to Repositories

Testing Coin Change Greedy Algorithm Implementation in hello-algo

A comprehensive test suite for validating the coin change greedy algorithm implementation in Go. This test verifies different scenarios of coin denomination combinations and their optimal solutions, demonstrating both successful and edge cases where greedy approach may not yield globally optimal results.

Test Coverage Overview

The test suite examines multiple coin denomination scenarios with varying complexity:

Optimal case with standard denominations (1,5,10,20,50,100)
Sub-optimal cases where greedy approach fails (1,20,50 and 1,49,50)
Edge cases demonstrating limitations of greedy algorithm

Implementation Analysis

Testing approach utilizes Go’s native testing framework with systematic validation of algorithm outcomes.

Multiple test cases within single function
Direct output validation using fmt.Printf
Comparative analysis between greedy results and actual optimal solutions

Technical Details

Test implementation leverages:

Go testing package (testing)
Standard fmt package for output formatting
Slice-based input structure for coin denominations
Integer-based amount validation

Best Practices Demonstrated

The test exhibits several quality testing practices:

Clear test case documentation
Explicit expected vs actual result comparison
Comprehensive edge case coverage
Well-structured test scenarios with increasing complexity

krahets/hello-algo

zh-hant/codes/go/chapter_greedy/coin_change_greedy_test.go

            
// File: coin_change_greedy_test.go
// Created Time: 2023-07-23
// Author: Reanon ([email protected])

package chapter_greedy

import (
	"fmt"
	"testing"
)

func TestCoinChangeGreedy(t *testing.T) {
	// 貪婪：能夠保證找到全域性最優解
	coins := []int{1, 5, 10, 20, 50, 100}
	amt := 186
	res := coinChangeGreedy(coins, amt)
	fmt.Printf("coins = %v, amt = %d\n", coins, amt)
	fmt.Printf("湊到 %d 所需的最少硬幣數量為 %d\n", amt, res)

	// 貪婪：無法保證找到全域性最優解
	coins = []int{1, 20, 50}
	amt = 60
	res = coinChangeGreedy(coins, amt)
	fmt.Printf("coins = %v, amt = %d\n", coins, amt)
	fmt.Printf("湊到 %d 所需的最少硬幣數量為 %d\n", amt, res)
	fmt.Println("實際上需要的最少數量為 3 ，即 20 + 20 + 20")

	// 貪婪：無法保證找到全域性最優解
	coins = []int{1, 49, 50}
	amt = 98
	res = coinChangeGreedy(coins, amt)
	fmt.Printf("coins = %v, amt = %d\n", coins, amt)
	fmt.Printf("湊到 %d 所需的最少硬幣數量為 %d\n", amt, res)
	fmt.Println("實際上需要的最少數量為 2 ，即 49 + 49")
}