白筱汐

想都是问题，做都是答案

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)
}