0 01背包问题

有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

题解

首先这个是动态规划的问题，并且是一个二维数组来决定。

动态规划三部曲：

1.定义dp数组和下标的含义 2.定义递推公式 3.递推公式的初始值和递归的顺序

首先我们分析怎么定义dp数组，首先我们必须要想到背包能装的最大价值其一是和背包的容量有关，其二和装的物品的重量和价值有关。所以要定义一个二维数组:dp[i][j]，表示为背包容量为j时，从0-i选择一些物品的最大价值。注意这里i并不是一定要取第i个物品，而是在0-i中任意选择。

递推公式：我们设想dp[i][j]的值和什么有关系。假设我们选择第i个物品，那么他的重量必须要考虑，所以背包剩余的容量j-weight[i]。选择第i个物品的价值 dp[i-1][j-weight[i]] + value[i], 不选第i个物品，就不会占用背包容量，也不会有价值产生，所以是dp[i][j] = dp[i-1][j]。那么我们需要比较到底放进第i个物品划算还是不放第i个物品划算，用 max(dp[i-1][j-weight[i]] + value[i], dp[i-1][j]) 来计算。

所以递推公式为： dp[i][j] = max(dp[i-1][j-weight[i]] + value[i], dp[i-1][j])

这其中还要考虑选择第i个物品是不是容量够放的问题，如果weight[i] > j，那么肯定是放不下，所以 dp[i][j] 只能等于 dp[i-1][j]

递推的初始值和递归顺序。
初始值:
如果j===0，那么一个物品都放不下（没有物品的重量是0），dp[i][0] = 0
如果i===0（选或者不选第一个物品，这里肯定选才能最大，除非背包容量不够），dp[0][j] = weight[0] > j ? 0 : value[0]

递归顺序：先递归物品，在递归背包容量？顺序无所谓，因为我们可以画图来说明问题。假设背包容量为4，有3个物品，对应的重量和价值是[1, 15], [3, 20], [4, 30]。先求出初始的dp 数组如下。

	1	2	3	4
物品0	15	15	15	15
物品1
物品2

从递归式来看，dp[i][j] 的值只取决于上一行同列的值或者同一行前面列的值。所以无论怎么遍历，这些值都是会被提前求出的。所以无论那种遍历顺序都是可以。

整体算法如下：

javascript

var maxValueOfBag = function(m, n, weights, values) {
    //m是物品，n是背包容量
    
    //初始化dp
    var dp = []
    for(let i=0;i<m;i++) {
        dp.push([])
        for(let j=0;j<=n;j++) {
            if (j===0) {
                //容量为0
                dp[i][j] = 0
            } else if(i===0) {
                //只选第一个物品
                dp[i][j] = weights[0] <= j ? values[0] : 0
            }
        }
    }
    //递推， 因为第一行和第一列已经初始化，所以可以从i=1,j=1开始
    for(let i=1;i<m;i++) {
        for(let j=1;j<=n;j++) {
            if(weights[i] > j) {
                //放不下该物品，只能不放
                dp[i][j] = dp[i-1][j]
            } else {
                dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j - weight[i]] + values[i])
            }
        }
    }

    return dp[m-1][n]
}

我们可以填充一下刚才的表格来看dp如何走的。

	1	2	3	4
物品0 (1,15)	15	15	15	15
物品1 (3,20)	15	15	20	35
物品2 (4,30)	15	15	20	35

题解2

空间优化的方案，我们在遍历的时候可以利用一维数组dp来表示背包容量为j时的最大价值。

三部曲： 1.dp含义和下标含义 2.递推公式 3.初始值和递推顺序

递推公式dp[j] = Math.max(dp[j], dp[j-weight[i]] + values[i]) 这里的dp[j] 其实是上一次的dp[j] ，也就是二维数组的dp[i-1][j] 初始值就是二维数组i=0时的初始值递推顺序比较重要，首先需要遍历物品，其次要遍历背包容量，容量要从高到低遍历。

javascript

var maxValueOfBagDP2 = function (m, n, weights, values) {
    var dp = []

    for (let i = 0; i <= n; i++) {
        if (weights[0] <= i) {
            dp[i] = values[0]
        } else {
            dp[i] = 0
        }
    }

    console.log('init dp', dp)
    //递推公式
    //dp[j] = Math.max(dp[j], dp[j-weight[i]] + values[i])
    for(let i=1;i<m;i++) {
        //必须按递减，否则就会重复计算两次
        for(let j=n;j>0;j--) {
            if (weights[i] > j) {
                //就直接复制上一次的值
                dp[j] = dp[j]
            } else {
                dp[j] = Math.max(dp[j], dp[j-weights[i]] + values[i])
            }
        }
        console.log('current dp '+ i, dp)
    }

    console.log('final dp', dp)

    return dp[n]
}

为什么要从高到低遍历，可以这样想，dp[j] 的值是从dp[j-weight[i]]+values[i]或者上一次的dp[j]获得，如果先从低到高遍历，那么dp[j] 的值就重复计算了（会变成拿好多次物品）。

0 01背包问题 ​

题解 ​

题解2 ​

0 01背包问题

题解

题解2