白筱汐

想都是问题,做都是答案

0%

动态规划(dp)- 背包问题

经典背包问题

假设你是一个贪婪的小偷,背着可装35磅重的背包,在商场伺机盗窃各种可装入背包的商品。吉他-1500$-15磅 笔记本电脑-2000$-20磅 音响-3000$-30磅。怎么选择商品,才能利益最大化呢?

如果使用贪心算法,每一步都选择最优解,第一次就偷了30磅的音响。虽然第一个操作是最优解,但是从全局来看,我们浪费了5磅的重量,因为没有小于等于5磅重量的商品可以偷了。

此时我们偷盗了价值3000$的商品,显然这不是利益最大化的选择。因为问题比较简单,我们很容易得出结果,偷取吉他和笔记本电脑是最优选择,可以偷到总价值3500$的商品。

我们需要使用动态规划(不懂的可以查看我写的爬楼梯问题文章),先解决子问题,再解决原来的问题。

我们需要建立一个二位数组dp网格。每一行描述当前商品,每一列描述当前可装重量。初始化所有单元格的值都为0,对于 i >= 1 && j >= 1 的每个单元格dp[i][j]都使用相同的计算公式:

dp[i][j] = Math.max(dp[i-1][j],dp[i - 1][j - weight[i - 1]] + value[i - 1])

这段代码描述的意思是:每个单元格的价格等于,上一个单元格的值与(当前商品的价格 + 剩余空间的价值)两者中的较大者。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// 吉他15磅 电脑20磅 音响30磅
const weight = [15,20,30]
// 吉他1500$ 电脑2000$ 音响3000$
const values = [1500,2000,3000]
const totalWeight = 35 // 总重量35磅

function maxValue(weight, value, totalWeight) {
const n = weight.length // n为物品个数
// 创建一个二位数组来保存状态转移的结果
// 注意数组的下标从0开始,需要对比上个单元格的值,所以二维数组的行数量为 n + 1,列数量为 totalWeight + 1
const dp = new Array(n + 1).fill(0).map(() => new Array(totalWeight + 1).fill(0))

for (let i = 1; i <= n; i++) {
for (let j = 1; j <= totalWeight; j++) {
// 如果当前物品小于等于剩余空间
if (weight[i - 1] <= j) {
// 比较(上一个单元格的值)和(当前物品的重量 + 剩余空间的价值)两者中较大的那个
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i - 1]] + value[i - 1])
} else {
// 当前物品大于剩余空间
dp[i][j] = dp[i - 1][j]
}
}
}
return dp[n][totalWeight];
}

go代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
package main

import "fmt"

func maxValue(weight []int, value []int, totalWeight int) int {
n := len(weight)
dp := make([][]int, n+1)
for i := range dp {
dp[i] = make([]int, totalWeight+1)
}
for i := 1; i <= n; i++ {
for j := 1; j <= totalWeight; j++ {
if weight[i-1] <= j {
// 比较(上一个单元格的值)和(当前物品的重量 + 剩余空间的价值)两者中较大的那个
dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i-1]]+value[i-1])
} else {
// 当前物品大于剩余空间
dp[i][j] = dp[i-1][j]
}
}
}
return dp[n][totalWeight]
}

// 比较函数 返回两者中的较大者
func max(a, b int) int {
if a > b {
return a
}
return b
}

func main() {
weight := []int{15, 20, 30}
value := []int{1500, 2000, 3000}
totalWeight := 35

total := maxValue(weight, value, totalWeight)
fmt.Println(total)
}