题解 | #【模板】01背包#

01简单背包

package main

import "fmt"

func main()  {
    var n, V int
    fmt.Scan(&n, &V)
    v := make([]int, n)
    w := make([]int, n)
    for i := 0; i < n; i++ {
        fmt.Scan(&v[i], &w[i])
    }
    solve1(n, V, v, w)
    solve2(n, V, v, w)
}

func maxInt(x, y int) int {
    if x > y {
        return x
    } else {
        return y
    }
}

func solve1(n int, V int, v, w []int) {
    dp := make([][]int, n+1)
    for i := range dp {
        dp[i] = make([]int, V+1)
    }
    for i := 1; i <= n; i++ {
        for j := 1; j <= V; j++ {
            if j >= v[i-1] {
                dp[i][j] = maxInt(dp[i-1][j], dp[i-1][j-v[i-1]] + w[i-1])
            } else {
                dp[i][j] = dp[i-1][j]
            }
        }
    }
    fmt.Println(dp[n][V])
}

func solve2(n int, V int, v, w []int) {
    dp := make([][]int, n+1)
    for i := range dp {
        dp[i] = make([]int, V+1)
    }
    for i := 1; i <= n; i++ {
        for j := 1; j <= V; j++ {
            if j < v[i-1] {
                dp[i][j] = dp[i-1][j]
            } else {
                if dp[i-1][j-v[i-1]] == 0 && v[i-1] != j {
                    dp[i][j] = dp[i-1][j]
                } else {
                    dp[i][j] = maxInt(dp[i-1][j], dp[i-1][j-v[i-1]] + w[i-1])
                }
            }
        }
    }
    
    fmt.Println(dp[n][V])
}