1. 二维动态规划的思路就不用多解释了，它的状态转移方程为：

dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]] + w[i])

含义：

(1) 如果不装第 $i$ 件物品，那么问题就转化为“前 $i-1$ 件物品放入容量为 $j$ 的背包中的最大价值”

(2) 如果装第 $i$ 件物品，那么问题就转化为“前 $i-1$ 件物品放入剩下的容量为 $j-v[i]$ 的背包中的最大价值”

2. 一维动态规划的状态转移方程（ $j$ 采取逆序的方式）

dp[j] = max(dp[j], dp[j - v[i]] + w[i])

其实两种做法，实现的思想是一样的，只不过一维数组更省空间，下面具体说说，为什么可以用一维数组来代替,而且要采取逆序的方式。

3.举例说明

假如枚举到：i = 3, j = 8, v[3] = 5, w[3] = 1

二维：dp[3][8] = max(dp[2][8], dp[2][3] + w[3])   此时的dp[2][8]和dp[2][3]都是上一轮的状态值

一维：dp[8] = max(dp[8], dp[3] + w[3])      我们要保证dp[8]和dp[3]都是上一轮的状态值

按照逆序的顺序，一维dp数组的更新顺序为：dp[8], dp[7], dp[6], ... , dp[3]

也就是说，在本轮更新的值，不会影响本轮中其他未更新的值！较小的index对应的状态是上一轮的状态值！

如果按照顺序进行更新，dp[3] = max(dp[3], dp[0] + w[0])，对dp[3]的状态进行了更新，那么在更新dp[8]时，用到的dp[3]
就不是上一轮的状态了，不满足动态规划的要求。

本思路来源于 https://www.cnblogs.com/lanhj/archive/2012/12/05/2802437.html

python3 代码

class Solution:
    def max_value(self, n, m, v, w):
        dp = [0] * (m + 1)
        for i in range(1, n + 1):
            for j in range(m, v[i] - 1, -1):  # j从m从大到小遍历到v[i]
                dp[j] = max(dp[j], dp[j - v[i]] + w[i])
        return dp[-1]


if __name__ == '__main__':
    import sys

    n, m = map(int, input().split())  # n表示物品个数，m表示最大体积
    v, w = [0], [0] # 因为从dp从1开始，所以开头填充0
    lines = sys.stdin.readlines()
    for line in lines:
        line = list(map(int, line.split()))
        v.append(line[0])
        w.append(line[1])
    print(Solution().max_value(n, m, v, w))

4. 降低代码复杂度

在执行动态规划的时候可以发现，遍历的顺序和接受输入的顺序是一致的，所以我们可以在接受每一行物品输入的同时，开始动态规划过程，而且每轮用到的v[i]和w[i]在下一轮中不会再用到，所以不需要存为数组形式。

简化版Python3代码如下：

 if __name__ == '__main__':
    n, m = map(int, input().split())
    dp = [0] * (m + 1)
    for i in range(1, n + 1):
        v, w = map(int, input().split())
        for j in range(m, v - 1, -1):
            dp[j] = max(dp[j], dp[j - v] + w)
    print(dp[m])