动态规划（二）：0-1背包

题目

有 件物品，每件占据的空间大小为 、价值为 ，对于容量空间为 的背包，问能够承载的最大价值是多少

分析

对于第 件物品，只有两种状态，放入背包，或不放入背包。所以在空间大小为 时，能够承载的最大价值根据第 件物品放入或不放入而定，且只有这两种情况。

解答

以 表示物品数量为 ，空间大小为 时的最大价值。则有：

1. 当 时有：，表示当前空间大小 无法容纳第一件物品，所以价值为 ；

2. 当 时有：，表示当前空间大小 可以容纳第一件物品，所以价值为 ；

3. 当 时有：，表示当前空间大小 无法容纳第 件物品，所以价值为 件物品时的价值 ；

4. 当 时有：，表示当前空间大小 可以容纳第 件物品，所以价值取决于第 件物品放入或不放入哪一种情况价值更大；

对于 件物品，空间大小为 时：

• 不放入第 件物品时价值为 ，即将所有空间 施加于前 件物品上；
• 放入第 件物品时，价值为 ，即第 件物品的价值与 空间下前 件物品的价值之和。

对于 01 背包问题，有两种描述，背包能够承载的最大价值、背包刚好装满时承载的最大价值。第二种描述增加了“装满”的条件约束，两种情况很类似，下面分别对无约束和有约束的情况进行讨论。

无装满约束

二维数组形式

def backpack(weightArr, valueArr, V):
    N = len(weightArr)
    arr = [[] for i in range(N)]  # Two-dimensional array
    for i in range(N):
        for j in range(V + 1): 
            if j < weightArr[i]:  # the space can not afford the element's weight
                arr[i].append(0 if i == 0 else arr[i - 1][j])
            else:  # the space can afford the element's weight
                if i == 0:  
                    arr[0].append(valueArr[0])
                else:
                    arr[i].append(max(arr[i - 1][j], arr[i - 1][j - weightArr[i]] + valueArr[i]))
        arr[i] = arr[i]
    return arr[-1][-1]

代码中存在两层循环，以二维数组的形式记录中间数据，分别记录不同物品个数在各个空间大小下的最大价值。循环内部存在两种判断，分别用于判断空间大小 是否能够容纳第 件物品，和判断当前是否是第一件物品。

• 若 ，即当前空间无法容纳第 件物品，则继续判断是否是第一件物品，若 ，即当前是第一件物品，则 ，表示当前空间大小无法容纳第一件物品，最大价值为 ；若 ，即当前不是第一件物品，则 ，表示当前空间大小无法容纳第 件物品，最大价值等同于没有第 件物品时候的最大价值；
• 若 ，即当前空间可以容纳第 件物品，则继续判断是否是第一件物品，若 ，即当前是第一件物品，则 ，表示当前空间可以容纳第一件物品，因为只有第一件物品，所以最大价值为 ；若 ，即当前不是第一件物品，则 ，比较第 件物品放入或不放入的价值，选择出最大价值。

代码中存在两层循环，时间复杂度为 ，使用了二维数组作为存储空间，空间复杂度为 。

观察推导公式：，可以发现 的值只与 和 有关，对应到二维数组中即为， 的值只与 和 有关。所以若已知二维数组第 行的数组 ，则推导第 行数组数据时，若从右向左推导，或者称为 值下标由大到小推导，则第 行数据可以覆盖在第 行数组。所以可以将二维数组空间优化为一维数组空间。

一维数组形式

def backpack2(weightArr, valueArr, V):
    N = len(weightArr)
    arr = [0] * (V + 1)  # One-dimensional array
    for i in range(N):
        for j in range(V, -1, -1):
            if j >= weightArr[i]:
                arr[j] = max(arr[j], arr[j - weightArr[i]] + valueArr[i])
    return arr[-1]

代码中仍存在两层循环，第二层循环中变量值 由大到小变化，循环体中仍存在判断，不过因为只存在一维数组，且数组元素初始化值为 ，所以不需要再判断是否是第一件物品。

代码中存在两层循环，时间复杂度为 ，使用了一维数组作为存储空间，空间复杂度为 。

其实无论一维数组或者二维数组形式，第二层循环范围不一定非要是 0 ~ ，因为此处只讨论 01 背包，所以若题目中给出的 值很大，大到即便将 件物品全部放入背包中，仍存在较大容量空闲的话，这种情况可以修改第二层循环范围为 0 ~ 。

有装满约束

二维数组形式

def backpackComplete(weightArr, valueArr, V):
    N = len(weightArr)
    arr = [[] for i in range(N)]  # Two-dimensional array
    for i in range(N):  
        for j in range(V + 1): 
            if j < weightArr[i]:  # the space can not afford the element's weight
                arr[i].append(arr[i - 1][j] if i > 0 else None)
            else:  # the space can afford the element's weight
                if i == 0:  
                    arr[0].append(valueArr[0] if j == weightArr[i] else None)
                else:
                    if arr[i - 1][j] and arr[i - 1][j - weightArr[i]]:  # the two values both exist
                        arr[i].append(max(arr[i - 1][j], arr[i - 1][j - weightArr[i]] + valueArr[i]))
                    elif not arr[i - 1][j] and not arr[i - 1][j - weightArr[i]]:  # the two values both not exist
                        arr[i].append(valueArr[i] if j == weightArr[i] else None)
                    else:  # only one value exist
                        arr[i].append(arr[i - 1][j] if arr[i - 1][j] else arr[i - 1][j - weightArr[i]] + valueArr[i])
        arr[i] = arr[i]
    return arr[-1][-1]

有装满约束与无装满约束较为类似，同样的两层循环，同样的两种判断。不同之处在于，当空间大小 不能刚好等于物品占据空间之和时，此时的价值为 。所以此处的代码相对于无装满约束的代码，最直观的差异就是，当空间大小 且 ，通过推导公式求最大价值时，对 和 是否为 进行了判断。

一维数组形式

def backpackComplete2(weightArr, valueArr, V):
    N = len(weightArr)
    arr = [None] * (V + 1)  # One-dimensional array
    for i in range(N):
        for j in range(V, -1, -1):
            if j >= weightArr[i]:
                if arr[j] and arr[j - weightArr[i]]:  # the two values both exist
                    arr[j] = max(arr[j], arr[j - weightArr[i]] + valueArr[i])
                elif not arr[j] and not arr[j - weightArr[i]]:  # the two values both not exist
                    arr[j] = valueArr[i] if j == weightArr[i] else None
                else:  # only one value exist
                    arr[j] = arr[j] if arr[j] else arr[j - weightArr[i]] + valueArr[i]
    return arr[-1]

比较有、无装满约束的一维数组形式，可以发现与二维数组同样的差异，即空间大小不刚好满足物品占据空间之和时，价值为 ，且对推导公式中的元素值进行了是否为 判断。

有、无装满约束，算法的时间复杂度和空间复杂度不变。不过可以发现一个很明显的地方：有装满约束时，数组的最后一项元素值 或 不一定是数组中的最大元素，而数组中的最大元素值一定等于无装满约束时数组的最后一项元素值。