对于传统的背包问题，假设N = 3, W = 4, 共有N个物体，背包能装的物品总重量W为4，wt = [2, 1, 3], val = [4, 2, 3]，wt表示N个物品各自的重量，val表示每个物品的价值，我们的最终目标是使得价值最大化（所装物品的总重量不超过W时，装进背包里面的物品的总val最大）。
套路解法：
明确【状态】和【选择】，对于背包问题就是【背包当前的容量】和【能被选择的物品有哪些】
选择就是【把当前物品装进背包中】和【当前物品不装进背包中】
套路代码：
背包问题画表格！！！
何时定义三维数组
dp[i][j][k]的定义如下：
若只使用前i个物品，当背包容量为j个0，k个1时，能够容纳的最多字符串数。
三维数组变二维，将遍历倒序
组合问题公式
dp[i] += dp[i-num]
True、False问题公式
dp[i] = dp[i] or dp[i-num]
最大最小问题公式
dp[i] = min(dp[i], dp[i-num]+1)或者dp[i] = max(dp[i], dp[i-num]+1)
以上三组公式是解决对应问题的核心公式。
当然拿到问题后，需要做到以下几个步骤：
1.分析是否为背包问题。
2.是以上三种背包问题中的哪一种。
3.是0-1背包问题还是完全背包问题。也就是题目给的nums数组中的元素是否可以重复使用。
4.如果是组合问题，是否需要考虑元素之间的顺序。需要考虑顺序有顺序的解法，不需要考虑顺序又有对应的解法。
接下来讲一下背包问题的判定
背包问题具备的特征：给定一个target，target可以是数字也可以是字符串，再给定一个数组nums，nums中装的可能是数字，也可能是字符串，问：能否使用nums中的元素做各种排列组合得到target。
背包问题技巧：
1.如果是0-1背包，即数组中的元素不可重复使用，nums放在外循环，target在内循环，且内循环倒序；
for num in nums:
for i in range(target, nums-1, -1):
2.如果是完全背包，即数组中的元素可重复使用，nums放在外循环，target在内循环。且内循环正序。
for num in nums:
for i in range(nums, target+1):
3.如果组合问题需考虑元素之间的顺序，需将target放在外循环，将nums放在内循环。
for i in range(1, target+1):
