大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE稳定放心使用
背景
- 0-1背包是非常经典的算法问题，很多场景都可以抽象成这个问题模型。这个问题的经典解法是动态规划。
- 不过还有一种简单但没有那么高效的解法，这里用的回溯算法。
- 0-1背包问题有很多变体，我这里介绍一种比较基础的。我们有一个背包，背包总的承载重量是Wkg。现在我们有n个物品，每个物品的重量不等，并且不可分割。 我们现在期望选择几件物品，装载到背包中。在不超过背包所能装载重量的前提下，如何让背包中物品的总重量最大?
- 实际上，假设物品是不可分割的，要么装要么不装，所以叫0-1背包问题。显然，这个问题已经无法通过贪心算法来解决了。我们现在来看看，用回溯算法如何来解决。
- 对于每个物品来说，都有两种选择，装进背包或者不装进背包。对于n个物品来说，总的装法就有2^n种，去掉总重量超过Wkg的，从剩下的装法中选择总重量最 接近Wkg的。不过，我们如何才能不重复地穷举出这2^n种装法呢?这里就可以用回溯的方法。
我们可以把物品依次排列，整个问题就分解为了n个阶段，每个阶段对应一个物品怎么选择。先对第一个物品进行处理，选择装进去或 者不装进去，然后再递归地处理剩下的物品。描述起来很费劲，我们直接看代码，反而会更加清晰一些。
代码如下
package main
import "fmt"
//总的思想是，把n个物体依次排列
//对每个当前物体考虑两种情况，一种是不放进入背包后，递归遍历后边的各种情况
//另一种是放进入背包后，再递归遍历后边的各种情况
//出递归条件，已经访问了最后一个物体了或者已经是背包最大容量了
var maxW int //表示背包能装的最大重量
var curAnswer []int //当前背包状态，下标表示物体，值表示是否装进背包
var bestAnswerMap = make(map[int][][]int) //存储最佳答案，key背包重量，值为多种情况，所以为数组
func f(i, cw int, items []int, n, w int) {
if curAnswer == nil { //其实只初始化了一次
curAnswer = make([]int, n) //curAnswer[x]值为1，表示x加入背包
}
if cw == w || i == n {
if cw != 0 && cw >= maxW { //cw是在背包允许的重量范围里的值，取其中最大值
maxW = cw
//如下是为了打印出最佳结果
bst := make([]int, n)
for j := 0; j < n; j++ {
bst[j] = curAnswer[j]
}
if val, ok := bestAnswerMap[maxW]; ok {
val = append(val, bst)
bestAnswerMap[maxW] = val
//map中的元素是不能寻址的，val,ok这种方式，拿到的是副本
} else {
temp := make([][]int, 0)
temp = append(temp, bst)
bestAnswerMap[maxW] = temp
}
//以上是为了打印出最佳结果
}
return
}
curAnswer[i] = 0 //考虑不放进入
f(i+1, cw, items, n, w) //考虑不放入当前物体的情况
if cw+items[i] <= w {
curAnswer[i] = 1 //考虑放进入背包
f(i+1, cw+items[i], items, n, w) //考虑放入当前物体的情况
}
}
func main() {
a := []int{1, 2, 3, 4, 10, 5, 6, 7, 8, 9}
f(0, 0, a, 10, 10)
fmt.Println(maxW)
for k, v := range bestAnswerMap {
fmt.Printf("key is %d, value is %v\n", k, v)
fmt.Println("=======================")
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/184329.html原文链接：https://javaforall.net
