编辑代码

/**
 * 
 * w:重量
 * v:价值
 * cap:背包容量
 */
function dynamicBackpack(w: Array<number>, v: Array<number>, cap: number) {
    const n = w.length
    //1. 构造二维数组 用于 dp表  行：背包容量，列： 背包重量
    const dp = Array(n + 1).fill(0)
        .map(() => Array(cap + 1).fill(0))

    // j：背包容量
    for (let i = 1; i <= n; i++) {
        for (let j = 1; j <= cap; j++) {
            if (w[i - 1] > j) {
                // 若超过背包容量，就不选物品i，选上一个
                dp[i][j] = dp[i - 1][j]
            } else {
                // 判断上一个大还是（当前容量-1）所装的最大重量 + 当前重量的大
                dp[i][j] = Math.max(
                    dp[i - 1][j],
                    dp[i - 1][j - w[i - 1]] + v[i - 1]
                )
            }
        }
    }
    console.log(dp)

    console.log(dp[n][cap])
}

const w = [1, 2, 3]
const v = [5, 10, 15]


/**
 * author: dxb
 */
dynamicBackpack(w, v, 4)