01背包草稿

# 背景介绍

一个最大承重为 W 的背包，以及一堆物品(重量 w,价值 v),求问该背包所装物品的最大价值？

# 状态转移方程

// dp[i][j] 表示空间为 j ,前 i 个的最大价值
// dp[i-1][j] 表示不放第 i 个时的最大价值
// dp[i-1][j-w[i]]+v[i] 表示放第 i 个时的最大价值
dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])

1
2
3
4

demo

// demo
w = [5,4,7,2,6] // 重量
v = [12,3,10,3,6] // 价值
W = 15 // 最大承重

// init
dp = Array(w.length).fill(0).map(()=>Array(W+1).fill(0))
for(let j=W;j>=w[0];j--){
  dp[0][j] = v[0]
}

// 开始计算
for(let i=1;i<w.length;i++){
  for(let j=W;j>=w[i];j--){
    dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])
  }
}

result = dp[w.length-1][W-1] // 本例结果为 25

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

因为每次计算的结果其实不依赖于之前的，可以进行状态压缩，得到

dp[j] = Math.max(dp[j],dp[j-w[i]]+v[i])

代码如下：

// demo
w = [5,4,7,2,6] // 重量
v = [12,3,10,3,6] // 价值
W = 15 // 最大承重

// init
dp = Array(W+1).fill(0)

// 开始计算
for(let i=0;i<w.length;i++){
  for(let j=W-1;j>=w[i];j--){
    dp[j] = Math.max(dp[j],dp[j-w[i]]+v[i])
  }
}

result = dp[W-1] // 本例结果为 25

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 获取所取物品列表

创建一个二维数组 path[][] ，取第 i 个元素会造成价值更大，则进行标记

path = Array(w.length).fill(0).map(()=>Array(W+1).fill(0))

for(let i=0;i<w.length;i++){
  for(let j=W;j>=w[i];j--){
    let tmp = dp[j-w[i]]+v[i]
    if(tmp > dp[j]){
      dp[j] = tmp
      // 进行标记
      path[i][j] = 1
    }
  }
}

// 从后向前找 若对应重量的背包被标记了 ，表示有放入该物品，扣除背包重量后向前找

let result = []
let curW = W
for(let i=w.length-1;i>=0;i--){
  if(path[i][curW] === 1){
    result.push(i)
    curW -=w[i]
  }
}
result.reverse() // result 即为最后

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

即可获得结果

编辑

上次更新: 2024/09/01, 23:56:56

← 前端插件架构设计 KMP→