Back to Repositories

Testing Knapsack Algorithm Implementations in hello-algo

This test suite implements and validates different knapsack problem solutions in Go, including both bounded and unbounded variants. It comprehensively tests dynamic programming implementations, memory-optimized versions, and recursive approaches for solving classic knapsack optimization problems.

Test Coverage Overview

The test suite provides extensive coverage of knapsack algorithm implementations.

Key areas tested include:

Standard knapsack problem with DFS approach
Memoized version of knapsack solution
Dynamic programming implementation
Space-optimized dynamic programming variant
Unbounded knapsack problem solutions

Implementation Analysis

The testing approach systematically validates multiple algorithmic implementations of the knapsack problem. Each test case utilizes Go’s testing framework to verify different solution strategies, from recursive DFS to optimized DP approaches. The test structure demonstrates clear separation between bounded and unbounded knapsack variants.

Technical Details

Testing tools and configuration:

Go testing package (testing.T)
fmt package for output validation
Dynamic memory allocation for memoization
Slice-based data structures for weights and values
Integer-based capacity constraints

Best Practices Demonstrated

The test implementation showcases several testing best practices.

Notable features include:

Clear test case organization
Comprehensive algorithm verification
Multiple implementation comparisons
Space and time complexity considerations
Systematic output validation

krahets/hello-algo

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