SOURCE

// 1、二维数组
function test_bag_problem() {
    let n=3,
        weight = [1, 3, 4],
        value = [15, 20, 30],
        bagweight = 4,
        dp = Array(n).fill(0).map(_ => Array(bagweight+1).fill(0))

    for(let i=0; i<=bagweight; i++) {
        if(i>=weight[0]) dp[0][i] = value[0]
    }

    for(let j=1; j<n; j++) {
        for(let i=0; i<=bagweight; i++) {
            if(weight[j] > i) dp[j][i] = dp[j-1][i]
            else dp[j][i] = Math.max(dp[j-1][i], dp[j-1][i - weight[j]] + value[j])
        }
    }
    console.log('dp:', dp)
    return dp[n-1][bagweight]
}

// 2、优化空间：一维数组
function test_bag_problem2() {
    let n=3,
        weight = [1, 3, 4],
        value = [15, 20, 30],
        bagweight = 4,
        dp = Array(bagweight+1).fill(0)

    for(let j=0; j<n; j++) {
        for(let i=bagweight; i>=weight[j]; i--) {
            dp[i] = Math.max(dp[i], dp[i - weight[j]] +value[j])
        }
    }
    console.log('dp2:', dp)
    return dp[bagweight+1]
}

test_bag_problem()
test_bag_problem2()