Go 代码

package main

import "fmt"

func main() {
    var n, m int // 表示 n 件物品，容量为 m 的背包
    fmt.Scanf("%d %d", &n, &m)

    a := make([]int, n) // 第 i 件物品的体积是 ai
    v := make([]int, n) // 第 i 件物品的价值是 vi

    for i := 0; i < n; i++ {
        fmt.Scanf("%d %d\n", &a[i], &v[i])
    }

    f := make([][]int, n+1) // 用前 i 个物品拼出重量 w 时最大总价值
    for i := range f {
        f[i] = make([]int, m+1)
    }

    f[0][0] = 0 // 0 个物品可以拼出重量 0，最大总价值是 0
    for i := 1; i <= m; i++ {
        f[0][i] = -1 // 0 个物品不能拼出大于 0 的重量，所以总价值设为 -1
    }

    for i := 1; i <= n; i++ { // 计算前 N 个物品拼出各种重量 0..M
        for w := 0; w <= m; w++ { // 的最大总价值 f[0..N][0..M]
            f[i][w] = f[i-1][w]
            if w >= a[i-1] && f[i-1][w-a[i-1]]!=-1 {
                f[i][w] = max(f[i][w], f[i-1][w-a[i-1]] + v[i-1])
            }
        }
    }

    var res int
    for w := 0; w <= m; w++ {
        if f[n][w] != -1 {
            res = max(res, f[n][w])
        }
    }
    fmt.Println(res)
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}