题解 | #【模板】01背包#
【模板】01背包
https://www.nowcoder.com/practice/fd55637d3f24484e96dad9e992d3f62e
package main import ( "fmt" ) func main() { n := 0 // 物品个数 v := 0 // 背包体积 fmt.Scan(&n, &v) N := n var vs []int // vs[i] 体积 var ws []int // ws[i] 价值 vi, wi := 0, 0 for n > 0 { fmt.Scan(&vi, &wi) vs = append(vs, vi) ws = append(ws, wi) n-- } solve1(N, v, vs, ws) solve2(N, v, vs, ws) } func solve2(N int, v int, vs, ws []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 < vs[i-1] { dp[i][j] = dp[i-1][j] } else { if dp[i - 1][j - vs[i-1]] == 0 && vs[i-1] != j { dp[i][j] = dp[i-1][j] } else { dp[i][j] = max(dp[i-1][j], dp[i-1][j-vs[i-1]] + ws[i-1]) } } } } fmt.Println(dp[N][v]) } func solve1(N int, v int, vs, ws []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 >= vs[i-1] { dp[i][j] = max(dp[i-1][j], dp[i-1][j-vs[i-1]]+ws[i-1]) } else { dp[i][j] = dp[i-1][j] } } } fmt.Println(dp[N][v]) } func max(a, b int) int { if a > b { return a } return b }
核心思路:
第一步明确“状态”和选择:
状态:背包的容量 和 可选择的物品
选择:装 or 不装
第二步明确dp数组的含义:
两个状态,所以用二维dp数组
dp[i][j] 定义如下:对于前i个物品,当前背包的容量为j,这种情况下可以装的最大价值是dp[i][j]
第三步根据“选择‘寻找状态转移的逻辑:
如果没装 dp[i][j] = dp[i-1][j]
如果装了 dp[i][j] = max(dp[i-1][j] , dp[i-1][j - vs[i - 1]] + vs[i - 1]) ;
#刷题日记#