Back to Repositories

Testing Greedy Coin Change Algorithm Implementation in hello-algo

This test suite evaluates the greedy coin change algorithm implementation in Go, examining both optimal and sub-optimal scenarios. It validates the algorithm’s behavior with different coin denominations and target amounts, demonstrating cases where greedy approach succeeds and fails to find the global optimum.

Test Coverage Overview

The test suite covers multiple scenarios for the coin change algorithm:

Optimal case with standard coin denominations (1,5,10,20,50,100)
Sub-optimal cases where greedy approach fails to find minimum coins
Edge cases with specific denomination sets (1,20,50) and (1,49,50)

Testing includes verification of both successful optimal solutions and identification of scenarios where greedy approach falls short.

Implementation Analysis

The testing approach utilizes Go’s native testing framework with systematic scenario validation.

Uses table-driven test patterns with predefined test cases
Implements formatted output verification using fmt package
Demonstrates both positive and negative test scenarios

The implementation specifically focuses on validating algorithm behavior against known optimal solutions.

Technical Details

Testing infrastructure includes:

Go testing package (testing.T)
fmt package for output formatting
Slice operations for coin denomination handling
Integer arithmetic for amount calculations

Best Practices Demonstrated

The test suite exemplifies several testing best practices:

Clear test case organization with distinct scenarios
Comprehensive documentation of expected vs actual results
Edge case coverage for algorithm limitations
Explicit output validation with formatted messages

krahets/hello-algo

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")
}