SOURCE

// 给你一个可装载重量为 W 的背包和 N 个物品，每个物品有重量和价值两个属性。
// 其中第 i 个物品的重量为 wt[i]，价值为 val[i]，
// 现在让你用这个背包装物品，最多能装的价值是多少？

/**
示例：
N = 3, W = 4
wt = [2, 1, 3]
val = [4, 2, 3]
 */

const knapsack = (N, W, wt, val) => {
    if (N <=0 || W <= 0) return 0;
    const dp = [];
    for (let i = 0; i < N; i++) {
        dp[i] = [];
        for (let j = 0; j < W; j++) {
            dp[0][j] = 0;
        }
        dp[i][0] = 0;
    }
    console.log('dp start', dp);
    for (let i = 1; i <= N; i++) {
        for (let j = 1; j<= W; j++) {
            if (W - wt[i - 1] < 0) {
                dp[i][j] = dp[i - 1][j];
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][W - wt[i-1]] + val[i - 1]);
            }
        }
    }
    console.log('dp end', dp);
}

knapsack(3, 4, [2, 1,3], [4, 2, 3]);