经典背包问题
假设你是一个贪婪的小偷,背着可装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
| const weight = [15,20,30]
const values = [1500,2000,3000] const totalWeight = 35
function maxValue(weight, value, totalWeight) { const n = weight.length 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) }
|