背包问题是一个非常典型的考察动态规划应用的题目，对其加上不同的限制和条件，可以衍生出诸多变种，若要全面理解动态规划，就必须对背包问题了如指掌。

01背包问题

题目描述

一个小偷面前有一堆（n个）财宝，每个财宝有重量w和价值v两种属性，而他的背包总容量为m，如何选取财宝，可以取得最大价值。

状态转移方程如下：
背包问题 - 图1

for w, v in n:
    # 此处不能从前往后遍历背包，
    # 因为从前往后的话，可能导致同一个财宝被放入背包多次
    for i in range(m, w - 1, -1):
        dp[i] = max(dp[i], v + dp[i - w])

如果每个财宝可以无限选用，则该问题称为完全背包问题。

动态转移方程如下：
背包问题 - 图6

for w, v in n:
    for i in range(w, m + 1): # 注意这一行，从前往后遍历
        dp[i] = max(dp[i], v + dp[i - w])

如果限定财宝**i**最多只能拿**k**个，则问题称为有界或多重背包问题。

动态转移方程如下：
背包问题 - 图7

for w, v in n:
    for i in range(m, w - 1, -1):
        for k in range(k + 1):
            dp[i] = max(dp[i], k*v + dp[i - k*w])