动态规划算法 – 0-1 背包问题 Python 讲解| Dynamic Programming Algorithm – 0-1 knapsack problem explained in Python

问题描述

有N个物品, 每个物品Cost为C[i], Value为W[i], 其中 i 属于 [0, …, N-1]
有一个书包, 容量为V
求书包能装下的最大Value

为什么叫0-1背包?

因为每个物品只有2选择: 不用(0)或者用(1). 物品不能重复使用.

暴力解法

暴力求解就是把N个物品的所有子集(Power Set)求出来, 然后看看所有Cost加起来是不是 <= 背包容量 V, 对满足以上条件的, 选出最大的Value.
子集一共有2^N个, 所以需要O(2^N)时间.
用DFS(深度优先搜索)的话, 需要O(N)空间

2维DP解法

这是一种背包固定套路, 首先初始化一个2维矩阵dp, N+1行, V+1列.

用 Python 表达出来就是

row = [0] * (1 + V)
dp = []
for i in range(N + 1):
    dp.append(list(row))

dp[i][v] 代表的意义是第0到第i-1个物品 (前i个物品), 容量为v的背包, 能放的最大价值
填格子的时候我们从左到右按行扫描, 也就是对一个特定物品, 第i-1个, 扫描所有可能的容量. 到第i-1个物品的时候, 容量为v的时候, 无非两种选择:
1. 把这个物品放进去, 那么v-C[i]需要大于或等于0, 否则放不下, 新的最大value为 dp[i-1][v-C[i]] + W[i]
2. 不把这个物品放进去. 为什么不放? 因为放不进了啊. value为 dp[i-1][v]

dp[i][v]需要放这两种情况中value大的那种. 用python表达就是, 先把dp[i][v]设成不放的情况, 如果可以放的话(v-C[i] >= 0), 并且放了Value增加了, 就换成放的情况. 用Python表达出来就是

for i in range(1, N + 1):
    for v in range(1, V + 1):
        dp[i][v] = dp[i - 1][v]
        if v - C[i] >= 0:
            dp[i][v] = max(
                dp[i][v], 
                dp[i - 1][v - C[i - 1]] + W[i - 1]
            )

注意下标有点tricky. dp[i][v]代表的意义是前i个物品, 所以最后一个物品的index是i-1 (物品下标从0开始). 这就是为什么要用C[i - 1], W[i - 1]. 很多纯理论算法用的是1 base的index, 转换成code的时候还有点麻烦. 我这里用的就直接是Python或大部分语言能跑的真code. dp[i][j] 赋值部分就是所谓的DP转移方程.

最后把初始化, 循环和转移方程连在一起, 就可以用 Python 完整的表达出来

def maxKnapsackValue(N, C, W, V):
    # init dp
    row = [0] * (1 + V)
    dp = []
    for i in range(N + 1):
        dp.append(list(row))

    for i in range(1, N + 1):
        for v in range(1, V + 1):
            dp[i][v] = dp[i - 1][v]
            if v - C[i - 1] >= 0:
                dp[i][v] = max(
                    dp[i][v], 
                    dp[i - 1][v - C[i - 1]] + W[i - 1]
                )
    return dp[N][V]

以上就是 Python 版本的0-1背包问题的2维DP套路解法

2维DP解法应用

以上总结的2维DP解法的模版可以直接应用在Leetcode 416上, 详细请看这篇文章.

参考资料

崔添翼 背包问题九讲 2.0 原文有些细节讲得不清楚, 而且有些伪代码转换成真代码时候有些问题, 本文用能run的真代码并试图把细节交代清楚.

Leave a Reply

Your email address will not be published. Required fields are marked *