N件物品和一个最多能被重量为W的状态转移方程

写在前面

问题描述

有 N 件物品和一个最大重量为 W 的背包。一件物品只有两个属性：重量和价值。第 i 项的权重为 weight[i]，结果值为 value[i]。每个物品只能使用一次，找出哪些物品放入背包的物品价值之和最大。

注意：0-1背包问题不能用贪心算法解决，也就是说不能通过先添加性价比最高的物品来进行优化，因为这种方法可能会造成背包空间的浪费，所以不能优化取得成就。

基本思想

有数量和价值两个变量。我们定义 dp[i][j] 表示第 i 项的体积不超过 j 可以达到的最大值。设第i个物品的体积为w，值为v。根据第i个物品是否有物品加入背包可以分两种情况讨论：

第 i 项可以添加也可以不添加，具体取决于最大值更大的情况。因此，0-1背包的状态转移方程为：

dp[i][j] = max(dp[i – 1][j], dp[i – 1][j – w] + v)

代码

// W 为背包总重量
// N 为物品数量
// weights 数组存储 N 个物品的重量
// values 数组存储 N 个物品的价值
public int knapsack(int W, int N, int[] weights, int[] values) {
    // dp[i][0]和dp[0][j]没有价值已经初始化0
    int[][] dp = new int[N + 1][W + 1];
    // 从dp[1][1]开始遍历填表
    for (int i = 1; i <= N; ++i) {
        // 第i件物品的重量和价值 
        int w = weights[i - 1], v = values[i - 1];
        for (int j = 1; j <= W; ++j) {
            if (j < w) {
                // 超过当前状态能装下的重量j
                dp[i][j] = dp[i - 1][j];
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weights[i]] + values[i]);
            }
        }
    }
    return dp[N][W];
}

dp[i][j]的值只和dp[i-1][0,...,j-1]有关0 1背包问题贪心算法，所以我们可以优化空间（即去掉dp的第一个维度） . 因此，0-1背包的状态转移方程为：dp[j] = max(dp[j], dp[j - w] + v)

特别注意：为了防止前一个循环的dp[0,...,j-1]被覆盖，循环中j只能反向遍历。优化空间复杂度：

ps：rolling array：就是让数组roll up，每次使用固定数量的存储空间来实现压缩，节省存储空间。

public int knapsack(int W, int N, int[] weights, int[] values) {
    int[] dp = new int[W + 1];
    for (int i = 1; i <= N; i++) {
        int w = weights[i - 1], v = values[i - 1];
        for (int j = W; j >= 1; --j) {
            if (j >= w) {
                dp[j] = Math.max(dp[j], dp[j - w] + v);
            }
        }
    }
    return dp[W];
}

ps：01对背包内圈的理解：简化为二维dp的时候就很容易理解了。一维dp是二维dp空间复用的结​​果。dp[i]=f(dp[i-num])，等式右边其实就是二维dp上面一行的数据，应该是只读的0 1背包问题贪心算法，读之前不要修改. 如果顺序为正，则后面的元素右边的dp可能会在读取前被修改，相反的顺序可以避免读取前被修改的问题。