背包九讲-Go详解

背包问题本质上是动态规划的一种，一般也是通过状态转移方程式来解决问题，问题一般是以一个有固定容量或者承重的背包和一些固定体积，重量和价值的物品，填充背包从而使背包中物品的价值最大化

01背包

01背包中每个物品只有选或不选两种状态

主要关键点：01背包的主要难点就是在于状态转移方程式的确定，这一点其实也是所有动态规划的难点所在，另一个就是为何物体的体积是逆序遍历的？

代码如下：

func main() {//背包容积var v int//物体数量var n intfmt.Scanf("%d", &n)fmt.Scanf("%d", &v)//物体体积vslice := make([]int, n,n)//物体价值wslice := make([]int, n,n)for i := 0; i < n; i++ {fmt.Scan(&vslice[i], &wslice[i])}//记录当前体积能装入的最大价值dp := make([]int, v+1, v+1)for i := 0; i < n; i++ {//体积从大到小开始遍历for j := v; j >=vslice[i]; j-- {//选择是否装入物品时的最大值进行更新dp[j] = int(math.Max(float64(dp[j]), float64(dp[j-vslice[i]]+wslice[i])))}}fmt.Println(dp[v])
}

完全背包

基本条件跟01背包类似，唯一不同的是每个物品可以无限次选择
代码如下：

主要的区别在于体积遍历时是从当前物品的体积开始遍历，与01背包相反

func main() {//背包容积var v int//物体数量var n intfmt.Scanf("%d", &n)fmt.Scanf("%d", &v)//物体体积vslice := make([]int, n,n)//物体价值wslice := make([]int, n,n)for i := 0; i < n; i++ {fmt.Scan(&vslice[i], &wslice[i])}dp := make([]int, v+1, v+1)for i := 0; i < n; i++ {//从小到大开始遍历for j := vslice[i]; j <= v; j++ {dp[j] = int(math.Max(float64(dp[j]), float64(dp[j-vslice[i]]+wslice[i])))}}fmt.Println(dp[v])
}

关于01背包和完全背包的具体讲解

1 状态转移方程式

dp是记录当前体积能装入物品的最大价值，下面这个状态转移方程式的主要含义是通过对比物品装入背包和不装入背包的最大价值

dp[j] = int(math.Max(float64(dp[j]), float64(dp[j-vslice[i]]+wslice[i])))

2 体积从大到小遍历和从小到大遍历

背包算法原理、主要的原因在于从大到小遍历时，当前的物品vslice[i]只有可能被选择一遍，就是在for j := v; j >=vslice[i]; j– 循环中当j == vslice[i]时
而从小到大遍历时，则可以使每个物体都可被多次选择

eg：

题目描述：

假设山洞里共有a,b,c,d ,e这5件宝物（不是5种宝物），它们的重量分别是2,2,6,5,4，它们的价值分别是6,3,5,4,6，现在给你个承重为10的背包, 怎么装背包，可以才能带走最多的财富。

有编号分别为a,b,c,d,e的五件物品，它们的重量分别是2,2,6,5,4，它们的价值分别是6,3,5,4,6，现在给你个承重为10的背包，如何让背包里装入的物品具有最大的价值总和？
按着这张图进行填写会发现说每个物体只会被使用一次

3 01背包和完全背包是所有背包问题的基础，了解了这两种背包问题后其他的背包问题都可解决

多重背包问题

相交于两种基础的背包问题，多重背包问题主要是在原本的基础上添加了物品个数限制
本质上也是01背包的实现,通过k * 体积来实现多个表示多个不同的物品

func main() {//背包容积var v int//物体数量var n intfmt.Scanf("%d", &n)fmt.Scanf("%d", &v)//物体体积vslice := make([]int, n,n)//物体价值wslice := make([]int, n,n)//物体个数sslice := make([]int, n,n)for i := 0; i < n; i++ {fmt.Scan(&vslice[i], &wslice[i], &sslice[i])}dp := make([]int, v+1, v+1)for i := 0; i < n; i++ {for j := v; j >= vslice[i]; j-- {for k := 1; k <=sslice[i]; k++ {if j >= k *vslice[i] {dp[j] = int(math.Max(float64(dp[j]), float64(dp[j-vslice[i] * k]+wslice[i]*k)))}}}}fmt.Println(dp[v])
}

当物品个数较大时，采用二进制将多重背包拆成01背包，例如1～10的数可以通过1 2 4 3四个数字组合得到（3 = 10 - 1 - 2 - 4得到）

type good struct {v intw int
}
func main() {//背包容积var v int//物体数量var n intfmt.Scanf("%d", &n)fmt.Scanf("%d", &v)goods := make([]good, n, n)for i := 0; i < n; i++ {//物体体积var vslice int//物体价值var wslice int//物体个数，物体范围较大var sslice intfmt.Scan(&vslice, &wslice, &sslice)for k := 1; k <= sslice; k*=2 {goods = append(goods, good{v: k * vslice,w: k * wslice,})sslice = sslice - k}if sslice > 0{goods = append(goods, good{v: sslice * vslice,w: sslice * wslice,})}}dp := make([]int, v+1, v+1)for i := 0; i < len(goods); i++{for j := v; j >=goods[i].v; j--{if j >= goods[i].v {dp[j] = int(math.Max(float64(dp[j]), float64(dp[j-goods[i].v]+goods[i].w)))}}}fmt.Println(dp[v])
}

混合背包问题

01背包与完全背包混合，多重背包转化为01背包

type num struct {v intw intkind int
}
func main() {//背包容积var v int//物体数量var n intfmt.Scanf("%d", &n)fmt.Scanf("%d", &v)nums := make([]num, n, n)for i := 0; i < n; i++ {//物体体积var vslice int//物体价值var wslice int//物体种类，var sslice intfmt.Scan(&vslice, &wslice, &sslice)if(sslice <= 0) {nums = append(nums, num{v:    vslice,w:    wslice,kind: sslice,})}else {for k := 1; k <= sslice; k*=2 {nums = append(nums, num{v: k * vslice,w: k * wslice,kind: -1,})sslice = sslice - k}if sslice > 0{nums = append(nums, num{v: sslice * vslice,w: sslice * wslice,kind: -1,})}}}dp := make([]int, v+1, v+1)for i := 0; i < len(nums); i++{if nums[i].kind < 0 {for j := v; j >=nums[i].v; j--{if j >= nums[i].v {dp[j] = int(math.Max(float64(dp[j]), float64(dp[j-nums[i].v]+nums[i].w)))}}}else {for j := nums[i].v; j <= v; j++ {dp[j] = int(math.Max(float64(dp[j]), float64(dp[j-nums[i].v]+nums[i].w)))}}}fmt.Println(dp[v])
}

二维背包问题

背包9讲，在原本的背包下多添加了一层重量限制

func main() {//背包容积var v int//物体数量var n int//背包最大重量var m intfmt.Scanf("%d", &n)fmt.Scanf("%d", &v)fmt.Scanf("%d", &m)//物体体积vslice := make([]int, n)//物体价值wslice := make([]int, n)//物品重量mslice := make([]int, n)for i := 0; i < n; i++ {fmt.Scan(&vslice[i], &mslice[i], &wslice[i])}//记录当前体积能装入的最大价值dp := make([][]int, v+1)for i := 0; i < len(dp); i++ {dp[i] = make([]int, m+1)}fmt.Println(len(dp), cap(dp), len(dp[0]), cap(dp[0]))for i := 0; i < n; i++ {//体积从大到小开始遍历for j := v; j >=vslice[i]; j-- {//判断当前背包容量是否大于装入物品体积, 这步可以省略//选择是否装入物品时的最大值进行更新for k := m; k >= mslice[i]; k-- {dp[j][k] = int(math.Max(float64(dp[j][k]), float64(dp[j-vslice[i]][k-mslice[i]]+wslice[i])))}}}fmt.Println(dp[v][m])
}

分组背包问题

其实也只是01背包的实现

func main() {//背包容积var v int//物体数量var n intfmt.Scanf("%d", &n)fmt.Scanf("%d", &v)dp := make([]int, v+1)for i := 0; i < n; i++ {//每组物品个数var s intfmt.Scanf("%d", &s)//物体体积vslice := make([]int, s,s)//物体价值wslice := make([]int, s,s)for t := 0; t < s; t++ {fmt.Scan(&vslice[t], &wslice[t])}for t := 0; t < s; t++ {//体积从大到小开始遍历for j := v; j >=vslice[t]; j-- {//判断当前背包容量是否大于装入物品体积, 这步可以省略//选择是否装入物品时的最大值进行更新dp[j] = int(math.Max(float64(dp[j]), float64(dp[j-vslice[t]]+wslice[t])))}}}fmt.Println(dp[v])
}

背包问题求方案数

func main()  {//背包容积var v int//物体数量var n intfmt.Scanf("%d", &n)fmt.Scanf("%d", &v)//物体体积vslice := make([]int, n,n)//物体价值wslice := make([]int, n,n)for i := 0; i < n; i++ {fmt.Scan(&vslice[i], &wslice[i])}//记录当前体积能装入的最大价值dp := make([]int, v+1, v+1)count := make([]int, v+1, v+1)for i := 0; i <= v; i++ {count[i] =1}for i := 0; i < n; i++ {//体积从大到小开始遍历for j := v; j >=vslice[i]; j-- {value := dp[j- vslice[i]] + wslice[i]if value > dp[j]{dp[j]=valuecount[j]=count[j-vslice[i]]}else {count[j]=(count[j-vslice[i]]+count[j])}}}fmt.Println(count[v])
}

图片来源参考：https://www.jianshu.com/p/0cf1f78ad043