背包问题.md

背包问题

leetcode 有变种，这道题是 lintcode 的 92 题 https://www.lintcode.com/problem/92/

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

举个简单的例子，输入如下：

N = 3(3个物品)

/**
* 0-1背包问题
* @param {Number} W 背包重量
* @param {Number} N 物品数量
* @param {Array} wt 物品重量数组
* @param {Array} val 物品价值数组
* @returns Number 背包能装的最大价值
*/
function knapsack(W, N, wt = [], val = []) {
    const dp = Array.from(new Array(N + 1), () => new Array(W + 1).fill(0));
    
    for (let i = 1; i <= N; i++) {
        for (let w = 1; w <= W; w++) {
            if (w - wt[i - 1] < 0) {
                dp[i][w] = dp[i - 1][w];
            }
            else {
                dp[i][w] = Math.max(
                    dp[i - 1][w],
                    // 这里的这个 dp[i - 1][w - wt[i - 1]] 和零钱兑换的那个条件差不多
                    // 应该是这类问题都是使用这种设定来解
                    dp[i - 1][w - wt[i - 1]] + val[i - 1]
                )
            }
        }
    }
    
    return dp[N][W];
}