LeetCode 动态规划专题 6：0-1 背包问题在空间复杂度

0-1 背包问题说的是这样一个问题：给定 个物品，还有这些物品对应的价值和重量。你有一个背包，背包限制重量 ，问你最多拿走的价值最多是多少的物品。这是一个带有约束的最优化问题，是动态规划能解决的问题。

第 1 步：定义状态。

的定义：考虑将索引的区间是 内的物品放进容积为 的背包，使得价值最大。注意：考虑将这 个物品放进容量为 的背包，使得价值最大。

第 2 步：推导出状态转移方程。于是对于 ， 有以下两种方案：

1、第 个物品没有被选择，则 为所求；

2、第 个物品被选择，则 为所求。

综合以上两点： 为所求，这个方程就称为状态转移方程。

时间复杂度：。
空间复杂度：。

我们这一节从空间复杂度进行优化。

优化1：基于第 行元素只依赖于第 行元素

由于第 行元素只依赖于第 行元素。理论上，只需要保持两行元素就可以了，为此我们采用“滚动变量”的方式。

Python 代码：

class Solution:
    def knapsack01(self, weights, values, capacity):
        '''
        一行一行填表
        # 填写第 0 行（只有 index = 0 这个物品）的时候，就看这个 index 的物品是否能放进背包
        # 如果可以放进背包，就是此时的最大价值


        :param weights:
        :param values:
        :param index:
        :param capacity:
        :return:
        '''

        l = len(weights)
        if l == 0:
            return 0
        dp = [[-1 for _ in range(capacity + 1)] for _ in range(2)]  # 我们只须要 2 行
        for i in range(capacity + 1):
            if weights[0] <= i:
                dp[0][i] = values[0]
            else:
                dp[0][i] = 0
        # 只要遇到 dp 跟 i 相关的索引的部分，都取 mod 2 的余数
        for i in range(1, l):
            for j in range(capacity + 1):
                dp[i % 2][j] = dp[(i - 1) % 2][j]
                if weights[i] <= j:
                    dp[i % 2][j] = values[i] + dp[(i - 1) % 2][j - weights[i]]
        return dp[(l - 1) % 2][-1]

优化2：如何将二维降到一维

依据：后面依赖前面的，因此，我们从右边向左边填写，所以可以用一行注意到：每一行的更新只和它左边的元素有关，我们把空间压缩到一行，执行动态规划的时候，从右边到左边更新就可以了。

Python 代码：

class Solution:
    def knapsack01(self, weights, values, capacity):
        '''
        :param weights:
        :param values:
        :param index:
        :param capacity:
        :return:
        '''

        l = len(weights)
        if l == 0:
            return 0
        # 我们只须要 1 行
        dp = [-1 for _ in range(capacity + 1)]
        for i in range(capacity + 1):
            if weights[0] <= i:
                dp[i] = values[0]
            else:
                dp[i] = 0
        for i in range(1, l):
            for j in range(capacity, -1, -1):
                if weights[i] <= j:
                    dp[j] = max(dp[j], values[i] + dp[j - weights[i]])
        return dp[-1]

（本节完）