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

【模板】01背包

http://www.nowcoder.com/practice/fd55637d3f24484e96dad9e992d3f62e

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])
}
全部评论

相关推荐

高斯林的信徒:武大简历挂?我勒个骚岗
点赞 评论 收藏
分享
迟缓的斜杠青年巴比Q了:简历被投过的公司卖出去了,我前两天遇到过更离谱的,打电话来问我有没有意向报班学Java学习,服了,还拿我学校一个学长在他们那报班学了之后干了华为OD当招牌
点赞 评论 收藏
分享
评论
1
1
分享

创作者周榜

更多
牛客网
牛客企业服务