1.优化搜索顺序
例如本题,我们先选择重量较重的猫,会使得后面的猫的选择性变少即使的分支的数量变少
例如背包问题 我们将体积大的物品放到背包里,后面选择物品的方案就会变少
2.排除等效沉余
例如问组合方案数量的问题,我们不会以排列的方式去寻找方案即顺序不会被考虑,为了实现这一点
我们在函数中引进了start参数保证后面遍历的数一定在start后面,不会在重复的选择某个数
例如1118分成互质组问题(1 3 5,4 9)是一种方案,而(4 9,1 3 5 )与前者是同样的方案,所以我们在遍历后加了一条判断语句
使的运行效率快了近50倍
3.可行性剪枝
如果在遍历过程中就发现不合法了就可以直接退出了
4.最优性剪枝
例如找到所消耗物品最小方案的一类问题中如果我们之前已经找到了一定的方案,并且把花费ans存储了下来,
当前遍历的方案的花费已经大于ans了,这里显然就可以直接退出了