方法1：暴力解法 //
每件物品可以放进包，也可以不放进包，时间复杂度O((2^n)*n)
方法2：动态规划
对于每件物品，都有2种选择，放进包和不放进包，分别计算这两种情况哪种包内的价值更大，取最大值
其状态如下图
根据上图状态可知，容积c和i构成数据对，可以定义一个二维数组来存储相应价值，如下图：
func max(v1, v2 int) int {
if v1 > v2 {
return v1
}
return v2
}
方法1：记忆化搜索
// 时间复杂度O(n*c)
// 空间复杂度O(n*c)
func knapsack2(w, v []int, c int) int {
n := len(w)
if n == 0 {
return 0
}
// (n*(c+1))二维数组
// memo[i][j]: 将[0...i]号物品,填充容量为j的背包的最大价值
memo := make([][]int, n)
for i := 0; i < n; i++ {
memo[i] = make([]int, c+1)
}
return bestValue2(w, v, n-1, c, n, memo)
}
// 将[0...index]号物品,填充容积为C的背包的最大价值
func bestValue2(w, v []int, index, c, n int, memo [][]int) int {
// 递归终止条件
if index < 0 || c < 0 {
return 0
}
// 如果计算过价值,直接返回该价值
if memo[index][c] != 0 {
return memo[index][c]
}
// 计算[0...index]物品放进容量c背包的最大价值
// 2种情况
// 情况1: index号物品不放进背包
res := bestValue2(w, v, index-1, c, n)
// 情况2: 如果背包有足够的空间,index号物品放进背包
if c >= w[index] {
res = max(res, v[index]+bestValue1(w, v, index-1, c-w[index], n))
}
// 存储结果
memo[index][c] = res
return res
}
根据状态方程得知,memo[i]行价值依赖memo[i-1]行结果,因此可以先求0行结果,
再求1行结果,一步步扩大,最终求出[0...n-1]行所有价值
方法2：动态规划
// 时间复杂度O(n*c)
// 空间复杂度O(n*c)
func knapsack3(w, v []int, c int) int {
n := len(w)
if n == 0 {
return 0
}
// (n*(c+1))二维数组
// memo[i][j]: 将[0...i]号物品,填充容量为j的背包的最大价值
memo := make([][]int, n)
for i := 0; i < n; i++ {
memo[i] = make([]int, c+1)
}
// 第0行的情况: 将[0...0]物品存进容量为c的背包
if w[0] <= c {
for i := w[0]; i <= c; i++ {
memo[0][i] = v[0]
}
}
// 第[1...length-1]行的情况
for i := 1; i < n; i++ {
// [0...i]物品,j空间
for j := 0; j <= c; j++ {
// 2种情况
// 情况1: index号物品不放进背包
memo[i][j] = memo[i-1][j]
// 情况2: 如果背包有足够的空间,index号物品放进背包
if j >= w[i] {
memo[i][j] = max(memo[i][j], v[i]+memo[i-1][j-w[i]])
}
}
}
return memo[n-1][c]
}
由方法2可知：第i行元素只依赖于i-1行元素,理论上,只需要保持两行元素即可求出最后一行价值
偶数行在memo[0],奇数行在memo[1]
方法3：动态规划优化1
// 时间复杂度O(n*c)
// 空间复杂度O(2*c)=O(c)
func knapsack4(w, v []int, c int) int {
n := len(w)
if n == 0 {
return 0
}
memo := make([][]int, 2)
for i := 0; i < 2; i++ {
memo[i] = make([]int, c+1)
}
if w[0] <= c {
for i := w[0]; i <= c; i++ {
memo[0][i] = v[0]
}
}
for i := 1; i < n; i++ {
i1 := i % 2 // 本行
i2 := (i - 1) % 2 // 上一行
for j := 0; j <= c; j++ {
memo[i1][j] = memo[i2][j]
if j >= w[i] {
memo[i1][j] = max(memo[i1][j], v[i]+memo[i2][j-w[i]])
}
}
}
return memo[(n-1)%2][c]
}
由方法3可知：i行素只参考i-1行上方和左边的元素，因此可以从右向左刷新 i 行内容
可以只用一行大小为c+1的数组完成动态规划
方法4：动态规划优化2
// 时间复杂度O(n*c)
// 空间复杂度O(c+1)
func knapsack5(w, v []int, c int) int {
length := len(w)
if length == 0 {
return 0
}
// memo[c]: 区间[0...index]的物品,填充容积c的背包的最大价值
// 空间(c+1)
memo := make([]int, c+1)
// 第0行的情况: 将[0...0]物品存进容量为c的背包
if w[0] <= c {
for i := w[0]; i <= c; i++ {
memo[i] = v[0]
}
}
for i := 1; i < length; i++ {
// i个物品,j空间,当j<w[i]时,小于w[i]值均不变,可以提前结束判断
for j := c; j >= w[i]; j-- {
memo[j] = max(memo[j], v[i]+memo[j-w[i]])
}
}
return memo[c]
}
测试4种实现方法的性能：
func main() {
w := []int{1, 2, 3}
v := []int{6, 10, 12}
t := time.Now()
fmt.Println(knapsack2(w, v, 5))
fmt.Println("记忆化搜索花费时间", t.Sub(time.Now()))
fmt.Println("========")
t = time.Now()
fmt.Println(knapsack3(w, v, 5))
fmt.Println("动态规划1花费时间", t.Sub(time.Now()))
fmt.Println("========")
t = time.Now()
fmt.Println(knapsack4(w, v, 5))
fmt.Println("动态规划2花费时间", t.Sub(time.Now()))
fmt.Println("========")
t = time.Now()
fmt.Println(knapsack5(w, v, 5))
fmt.Println("动态规划2花费时间", t.Sub(time.Now()))
}
// 测试结果
22
记忆化搜索花费时间 -102.325µs
========
22
动态规划1花费时间 -13.581µs
========
22
动态规划2花费时间 -1.596µs
========
22
动态规划2花费时间 -1.346µs
继下一篇《(30)Go动态规划背包思想求解问题》https://www.jianshu.com/p/2f32ad93ee3e
有bug欢迎指出
网友评论