[数据结构与算法]01背包问题

一、0-1背包问题的状态转移方程

设F(n, C)考虑将n个物品放进容量为C的背包中，使得价值最大。
对于F(i, c)有两种选择：
（1）对于第i个物品不需要放入背包中，则该问题就变成F(i - 1, c)
（2）对于第i个物品需要放入背包中，则该问题就变成F(i - 1, c - w(i)) + v(i)
在二种选择选择最大值就为01背包的解，为：

F(i, c) = max(F(i - 1, c), F(i - 1, c - w(i)) + v(i))

时间复杂度：O(n * c)；空间复杂度：O(n * c)
代码如下

private static int bestValueDynamic(int[] w, int[] v) {
    int[][] res = new int[n][c + 1];

    for (int i = 0; i <= c; i ++) {
        res[0][i] = i >= w[0] ? v[0] : 0;
    }

    for (int i = 1; i < n; i ++) {
        for (int j = 0; j <= c; j ++) {
            res[i][j] = res[i - 1][j];
            if (j >= w[i]) {
                res[i][j] = Math.max(res[i][j], v[i] + res[i - 1][j - w[i]]);
            }
        }
    }
    return res[n - 1][c];
}

二、算法的优化

根据状态转移方程，第i行元素只依赖于第i-1行元素，因此理论上只需要保持两行矩阵即可。则空间复杂度就为O(n)。

同时由于一个元素只依赖自己左边的元素，因此就需要一维数组即可，但是需要逆序遍历。
代码实现：

// 动态规划的优化，只使用一维数组，只参考上边和左边的内容，可以只用一个一维数组，需要逆序遍历
// 时间复杂度：O(n * c)；空间复杂度：O(n)
private static int bestValueDynamic(int[] w, int[] v) {
    int[] res = new int[c + 1];

    for (int i = 0; i <= c; i ++) {
        res[i] = i >= w[0] ? v[0] : 0;
    }

    for (int i = 1; i < n; i ++) {
        for (int j = c; j >= w[i]; j --) {
            res[j] = Math.max(res[j], v[i] + res[j - w[i]]);
        }
    }
    return res[c];
}

三、0-1背包的变种

完全背包的问题：每个物品可以无限使用

多重背包问题：每个物品不止一个，有nums[i]个

多维费用背包问题：要考虑物品的体积和重量两个维度

四、leetcode相关题目

416、474、377、139、494

五、关于0-1背包地思考

在leetcode很多题目本质上就是0-1背包问题，例如一类问题就是从一个数组中选出数的和为一个给定值，这就是一个0-1背包问题。此外0-1背包分为以下几种：
1、只在乎最大价值，这类问题就是以上讨论的；
2、保证容量被装满，这类问题就是组合和问题，在这类问题中，也需要区分顺序问题和重复问题。
（1）如果不考虑顺序和重复，就是排列和问题，例如leetcode 377。
状态方程为：

F(s) = sum(F(s - num[i]))

代码为：

// target就是背包容量
int[] res = new int[c + 1];
res[0] = 1;
for (int j = 1; j <= c; j ++) {
    for (int i = 0; i < nums.length; i ++) {
        if (j >= nums[i]) {
            res[j] += res[j - nums[i]];
        }
    }
}

（2）考虑顺序，元素可以无限使用，就是完全背包问题，例如leetcode 518
状态方程为：F(k,i) = F(k-1, i) + F(k - 1, i-nums[k])
F(k,i)表示k个数可以凑成i的方法数，分为两种情况
代码为：

int[] res = new int[c + 1];
res[0] = 1;
for (int num : nums) {
    for (int i = num; i <= c; i ++) {
        res[i] += res[i - num];
    }
}

（3）元素只能使用一次，就是01背包问题，例如leetcode494
代码为：

int[] res = new int[c + 1];
res[0] = 1;
for (int i = 0; i < nums.length; i ++) {
    for (int j = c; j >= nums[i]; j --) {
        res[j] += res[j - nums[i]];
    }
}

我们可以看出以上的状态方程是一致的，只要是代码循环方式不一致。