golang 背包算法

Go 语言中的背包问题（Knapsack Problem）通常是指动态规划算法的一个应用实例，它涉及到在给定容量限制下选择物品以获得最大的价值。在 Go 中解决背包问题，你需要定义一个二维数组或矩阵，其中每个元素 `(i, j)` 表示前 i 个物品中有价值 j 的物品可以选择。常见的解决方案包括：

1. 动态规划：通过填充值表 `dp[i][j]`，计算包含前 i 个物品且总重量不超过 j 时的最大价值。初始条件通常是 `dp[0][j] = 0` 和 `dp[i][0]` 等于不包含第 i 个物品的价值。

func knapSack(W int, wt []int, val []int, n int) int {
    dp := make([][]int, n+1)
    for i := range dp {
        dp[i] = make([]int, W+1)
    }

    for i := 1; i <= n; i++ {
        for w := 1; w <= W; w++ {
            if wt[i-1] <= w {
                dp[i][w] = max(dp[i-1][w], dp[i-1][w-wt[i-1]] + val[i-1])
            } else {
                dp[i][w] = dp[i-1][w]
            }
        }
    }

    return dp[n][W]
}

// 定义辅助函数 max(a, b)
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

2. 回溯法：这是一种递归解法，从最大值开始尝试添加物品，直到达到容量限制。

func backtracking(W int, wt []int, val []int, n int, currWeight int, dp [][]bool) bool {
    if currWeight == W || n == 0 {
        dp[n][currWeight] = true
        return dp[n][currWeight]
    }
    
    dp[n][currWeight] = dp[n-1][currWeight]
    if wt[n-1] <= currWeight {
        dp[n][currWeight] |= backtracking(W, wt, val, n-1, currWeight-wt[n-1], dp)
    }

    return dp[n][currWeight]
}

// 初始化dp数组
var dp [][2]int = make([][]bool, n+1)