Back to Repositories

Testing Dynamic Programming Knapsack Implementations in hello-algo

This test suite implements and validates various knapsack problem algorithms using dynamic programming approaches in Go. It covers both classic and unbounded knapsack problems, demonstrating different optimization techniques including brute force, memoization, and space-optimized solutions.

Test Coverage Overview

The test suite provides comprehensive coverage of knapsack algorithm implementations.

Tests both classic and unbounded knapsack problems
Validates multiple solution approaches including DFS, memoization, and dynamic programming
Verifies space-optimized implementations
Tests with various weight and value combinations

Implementation Analysis

The testing approach employs Go’s native testing framework to validate different knapsack algorithm implementations.

Key patterns include:

Systematic comparison of different solution approaches
Memory optimization testing
Performance validation across different input sizes
Clear output verification using fmt.Printf

Technical Details

Testing infrastructure includes:

Go testing package (testing.T)
fmt package for output validation
Dynamic slice initialization for memoization
Matrix-based state storage for DP solutions

Best Practices Demonstrated

The test suite exemplifies high-quality testing practices.

Separate test functions for different knapsack variants
Clear test case organization
Comprehensive algorithm verification
Efficient memory management testing
Consistent output validation

krahets/hello-algo

zh-hant/codes/go/chapter_dynamic_programming/knapsack_test.go

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

package chapter_dynamic_programming

import (
	"fmt"
	"testing"
)

func TestKnapsack(t *testing.T) {
	wgt := []int{10, 20, 30, 40, 50}
	val := []int{50, 120, 150, 210, 240}
	c := 50
	n := len(wgt)

	// 暴力搜尋
	res := knapsackDFS(wgt, val, n, c)
	fmt.Printf("不超過背包容量的最大物品價值為 %d\n", res)

	// 記憶化搜尋
	mem := make([][]int, n+1)
	for i := 0; i <= n; i++ {
		mem[i] = make([]int, c+1)
		for j := 0; j <= c; j++ {
			mem[i][j] = -1
		}
	}
	res = knapsackDFSMem(wgt, val, mem, n, c)
	fmt.Printf("不超過背包容量的最大物品價值為 %d\n", res)

	// 動態規劃
	res = knapsackDP(wgt, val, c)
	fmt.Printf("不超過背包容量的最大物品價值為 %d\n", res)

	// 空間最佳化後的動態規劃
	res = knapsackDPComp(wgt, val, c)
	fmt.Printf("不超過背包容量的最大物品價值為 %d\n", res)
}

func TestUnboundedKnapsack(t *testing.T) {
	wgt := []int{1, 2, 3}
	val := []int{5, 11, 15}
	c := 4

	// 動態規劃
	res := unboundedKnapsackDP(wgt, val, c)
	fmt.Printf("不超過背包容量的最大物品價值為 %d\n", res)

	// 空間最佳化後的動態規劃
	res = unboundedKnapsackDPComp(wgt, val, c)
	fmt.Printf("不超過背包容量的最大物品價值為 %d\n", res)
}