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

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]) ;