题解 | 【模板】01背包

package main

import (
    "fmt"
)

func main() {
    var n,v int
    fmt.Scan(&n, &v)
    value := make([]int, n)
    weight := make([]int, n)
    for i:=0;i<n;i++ {
        fmt.Scan(&weight[i])
        fmt.Scan(&value[i])
    }
    dp := make([]int, v+1)
    for i:=0;i<n;i++ {
        for j:=v;j-weight[i] >= 0;j-- {
            dp[j] = max(dp[j], dp[j-weight[i]] + value[i])
        }
    }
    dp2 := make([]int, v+1)
    for i:=0;i<v+1;i++ {
        dp2[i] = -9999
    }
    dp2[0]=0
    // for i:=0;i<n;i++ {
    //     dp2[weight[i]] = max(dp2[weight[i]], value[i])
    // }
    for i:=0;i<n;i++ {
        for j:=v;j-weight[i] >= 0;j-- {
            // if dp2[weight[i]] > 
            dp2[j] = max(dp2[j], dp2[j-weight[i]] + value[i])
        }
    }
    // fmt.Println(dp)
    // fmt.Println(dp2)
    fmt.Println(dp[v])
    if dp2[v] > 0 {
        fmt.Println(dp2[v])
    } else {
        fmt.Println(0)
    }
}

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