01背包问题
有n个物品，1个容量v的背包，第i个物品体积是volume[i]，价值是value[i]，问将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大，每个物品只能应用1次。
思考中间状态，有i个物品，有j个容量，该状态的最高价值为status[i][j]。该状态能够由其上一个状态转移取得，对于第i个物品，咱们能够将其抛弃或放入背包，取两者最大值。
抛弃：status[i][j] = status[i-1][j]
放入：status[i][j] = value[i] + status[i-1][j-volume[i]]
这里的（i，j）状态，是第i个物品曾经做出抉择的后果，他须要上一个状态即抉择第i-1个物品后的后果转移而来。j - volume[i]能够了解为，抉择物品i后的容量是j，那么未抉择之前为j - volume[i]。
def solution(n, v, volume, value): status = [[0]*(v+1) for _ in range(n+1)] for i in range(1, n+1): for j in range(1, v+1): if j - volume[i-1] >= 0: status[i][j] = max(status[i-1][j], value[i-1] + status[i-1][j-volume[i-1]]) else: status[i][j] = status[i-1][j] return status[n][v]对于矩阵status，其状态只在i-1和i两行之间转移，咱们能够应用滚动数组也就是只用两行来一直地更新，保护上一步和以后步的状态，以达到升高空间复杂度的目标。
这里应用状态压缩，只用一行来记录状态，将二维DP降到一维DP。将下面的代码稍作改变，能够失去上面的错误代码，这里只是单纯的把i状态删掉了。尽管是谬误的代码，但咱们须要它来辅助了解。
def solution(n, v, volume, value): status = [0]*(v+1) for i in range(1, n+1): for j in range(1， v+1): if j - volume[i-1] >= 0: status[j] = max(status[j], value[i-1] + status[j-volume[i-1]]) else: status[j] = status[j] return status[v]该段代码的问题在于，对于status[j]的计算须要依赖于status[j-volume[i]]的后果，在二维中，status[j]和status[j-volume[i]]是别离处于不同行的，也就是i与i-1两行，然而在一维中，它们都在同一行。
并且j值是向右增长的，也就是说在计算status[j]时，status[j-volume[i]]的值早已被更新为第i行的状态了，而不是上一步的状态。所以咱们须要让j值向左增长。失去如下代码。
def solution(n, v, volume, value): status = [0]*(v+1) for i in range(1, n+1): for j in range(v, 0, -1): if j - volume[i-1] >= 0: status[j] = max(status[j], value[i-1] + status[j-volume[i-1]]) else: status[j] = status[j] return status[v]这段代码曾经是正确的了，然而还不够完满，察看后不难发现status[j] = status[j]这一步是齐全没有必要存在的，因而咱们能够管制j的最小值，保障j - volume[i-1] >= 0成立。失去最终代码如下。
def solution(n, v, volume, value): status = [0]*(v+1) for i in range(1, n+1): for j in range(v, volume[i-1]-1, -1): status[j] = max(status[j], value[i-1] + status[j-volume[i-1]]) return status[v]之所以该问题被称作01背包，其起因在于对于每一样物品只能应用一次。在咱们遇到的题目中，往往是01背包问题的变体，咱们须要学会如何将题目转换为经典的01背包问题。
相干题目：宰割等和子集、一和零、最初一块石头的分量 II。