背包问题
假设山洞里共有a, b, c, d, e这5件宝物（不是5种宝物），它们的重量分别是2, 3, 4, 4, 6，它们的价值分别是5, 4, 6, 3, 6 现在给你个承重为10的背包, 怎么装背包，可以才能带走最多的财富。
问题分析
这个问题俗称01背包，由于这5件物品都是唯一的，所以对于每个物品，我们对他的操作只有 拿了 or 没拿；可以用0表示 没放入包里；用1表示放进了包里
比如我们把 a,b,c 放进了背包， 那么可以表示为 1 1 1 0 0 转成10进制为28； 把a,c,e放进了背包可以认为是1 0 1 0 1转十进制为21， 全放进去为1 1 1 1 1 转10进制为63
所以我们只要遍历每一种可能， 然后验证这种可能的组合质量是不是小于10， 然后在进一步计算出该组合的价值，然后跟其他符合条件的组合产生的价值比较，取最大的即可
代码：
package main
import "fmt"
func main() {
arrWeight := [5]int{2, 3, 4, 4, 6} // 物品质量
arrValue := [5]int{5, 4, 6, 3, 6} // 对应价值
bagCapacity := 10 //背包容量
maxValue := 0
n := 1<<len(arrWeight) - 1 //复杂度2^n-1
for i := 1; i < n; i++ {
weight := getWeight(i, arrWeight[:])
if weight < bagCapacity {
thisValue := getValue(i, arrValue[:])
if maxValue < thisValue {
maxValue = thisValue
}
}
}
fmt.Println(maxValue)
}
func getWeight(bitmap int, arrWeight []int) int {
i := 1
weight := 0
len := len(arrWeight)
for {
if bitmap == 0 {
break
}
if bitmap&1 == 1 {
j := len - i
weight = weight + arrWeight[j]
}
bitmap = bitmap >> 1
i++
}
return weight
}
func getValue(bitmap int, arrValue []int) int {
i := 1
value := 0
len := len(arrValue)
for {
if bitmap == 0 {
break
}
if bitmap&1 == 1 {
j := len - i
value += arrValue[j]
}
bitmap = bitmap >> 1
i++
}
return value
}
进一步分析
如果我们按照上述思路，穷举暴力解决， 算法复杂度为2n-1
仔细观察， 如果放入了D，E 则表达式为 0 0 0 1 1; 就再也放不了别的物品了， 穷举的时候1 0 0 1 1和1 1 0 1 1 等情况都是没有意义的计算， 很明显算法有更进一步的优化空间
按照这个思路， 我们可以依次放入物品，只要总重量小于背包承载重量， 就放入下一个物品，当放入下一个物品质量超出了背包所能承受的重量，那么任何该组合下其他种可能都不用再尝试，接下来，放弃该物品，放入下一个物品， 直到尝试到最后一个物品；
然后拿掉第一个放入的物品，在剩余的四个物品中（产生新的组合）， 再次尝试上述操作， 直到剩余物品组合个数为0
package main
import "fmt"
func main() {
arrWeight := [5]int{2, 3, 4, 4, 6} // 物品质量
arrValue := [5]int{5, 4, 6, 3, 6} // 对应价值
bagCapacity := 10 //背包容量
maxValue := knapsack(arrWeight[:], arrValue[:], bagCapacity)
fmt.Println(maxValue)
}
// func knapsack(arrWeight []int, arrValue []int, bagCapacity int) int {
// if bagCapacity == 0 {
// return 0
// }
// maxValue := 0
// n := len(arrWeight)
// if n > 0 {
// fmt.Println(666)
// if arrWeight[0] <= bagCapacity {
// maxValue += arrValue[0]
// if n > 1 {
// maxValue += knapsack(arrWeight[1:], arrValue[1:], bagCapacity-arrWeight[0])
// }
// }
// if n > 1 {
// newMaxvalue := knapsack(arrWeight[1:], arrValue[1:], bagCapacity)
// if newMaxvalue > maxValue {
// maxValue = newMaxvalue
// }
// }
// }
// return maxValue
// }
func knapsack(arrWeight []int, arrValue []int, bagCapacity int) int {
weight := 0
maxValue := 0
n := len(arrWeight)
if n > 0 {
for i := 0; i < n; i++ {
newWeight := weight + arrWeight[i]
if newWeight < bagCapacity {
weight += arrWeight[i]
maxValue += arrValue[i]
} else {
if i+1 < n {
maxValue += knapsack(arrWeight[i+1:], arrValue[i+1:], bagCapacity-weight)
break
}
}
}
newMaxvalue := knapsack(arrWeight[1:], arrValue[1:], bagCapacity)
if newMaxvalue > maxValue {
maxValue = newMaxvalue
}
}
return maxValue
}
上面的解决方案是以质量为参考，也有按价值， 以及按价值/质量比，排序后再进行演算
其他背包模型
本文中仅探讨了 01背包； 还有其他背包模型
完全背包问题
现在有A，B，C，D，E…..等 N种物品， 每种物品都有n个；质量分别是Aw，Bw，Cw，Dw，Ew….; 价值为Av，Bv, Cv, Dv, Ev……; 现在给出一个承载质量为M的背包，如何装能让包中的物品价值最大化
背包求解
现在有物品A，B，C，D，E种物品， 质量分别为Aw，Bw，Cw，Dw，Ew； 现在有一个包，包里装有上述物品，每件物品最多一个，总质量为M；在不打开背包的情况下，求背包里可能装的都是哪些物品