背包问题复盘

0 背包类型

1. 0-1背包：每个物品只能放入一次
2. 完全背包：每个物品放入无数次
3. 多重背包：每个物品最多放入背包n次

1 求装满背包有多少种实现方法

1. dp[0] 初始化为 1
2. 递推公式：

if ( j >= weight[i]) {
    dp[j] += dp[j - weight[i]]
}

2 有关遍历顺序

常规为先遍历物品后遍历背包

0-1背包

至于先背包后物品究竟是否可行，取决于最原始的二维dp数组的递推公式所依赖的项的生成先后

完全背包

先物品后背包：得到所有组合，组合不考虑顺序：[1, 2] 和 [2, 1] 是一种

先背包后物品：得到所有排列，排列考虑顺序：[1, 2] 和 [2, 1] 是两种