0-1 背包模板

• 使用二维数组
  • 先遍历背包容量，后遍历物品，或者相反，都可以
• 使用一维数组
  • 外层遍历物品，内层遍历背包容量
  • 内层必须逆序遍历，否则变成完全背包

完全背包

• 使用一维数组
  • 外层遍历物品，内层遍历背包容量
  • 内层必须顺序遍历，否则变成0-1背包
• 求排列数、组合数
  • 若求组合数，那么外层遍历物品，保证相同组合只出现一次
  • 若求排列数，外层遍历背包容量，保证相同排列可以出现多次