一：剪枝策略的寻找的方法
1 )微观方法)从问题本身出发，发现剪枝条件
2 )宏观方法)整体发现剪枝条件。
3 )注意提高效率是关键、最重要的。
总之，剪枝策略，属于算法优化范畴；通常应用在DFS 和 BFS 搜索算法中；剪枝策略就是寻找过滤条件，提前减少不必要的搜索路径。
二：剪枝算法(算法优化)
1、个人资料
在搜索算法中优化中，剪枝，就是通过某种判断，避免一些不必要的遍历过程在形象上是因为切掉了检索树中的几个“树枝”而被称为剪枝。应用剪枝优化的核心问题是设计剪枝判断方法，即确定哪些枝条应当舍弃，哪些枝条应当保留的方法。
2、剪枝优化三原则： 正确、准确、高效.原则
搜索算法大部分都需要剪枝。 但并不是所有的树枝都可以砍下，需要通过设计合理的判断方法来决定一个树枝的取舍。 在设计判断方法时，需要遵循一定的原则。
剪枝的原则
1 )正确性
如上所述，树枝是不喜欢剪的.如果随便剪树枝，一直剪到有最优解的树枝，剪了树枝也就没有意义了.所以，前提是不失去正确的结果.
2 )准确性
在保证正确性的前提下，应具体分析具体问题，采用合适的判断手段，尽可能多地截取不含最优解的树枝，达到“优化”程序的目的.剪枝的准确性，是衡量一个优化算法好坏的标准
3 )效率
设计优化程序的根本目的，是要减少搜索的次数，使程序运行的时间减少. 但为了使搜索次数尽可能的减少，我们又必须花工夫设计出一个准确性较高的优化算法，而当算法的准确性升高，其判断的次数必定增多，从而又导致耗时的增多，这便引出了矛盾.因此，通过取得最优化和效率的平衡，尽量降低程序的时间复杂度也是非常重要的。 尽管剪枝的判断效果非常好，但如果在判断、比较上花了很多时间，其结果与程序整体没有被最优化的情况相差很大，那就太吃亏了。
3、分类
剪枝算法根据其判断思路，可以大致分为：可行性剪枝和最优性剪枝两大类。
3.1 可行性剪枝——该方法继续搜索以确定是否可以获得答案，如果不能直接追溯。
3.2 最优性剪枝
最佳性剪枝，又称上下限剪枝，是一种重要的搜索剪枝策略。 可以记录当前得到的最佳值，在当前节点不能生成比当前的最佳解更好的解的情况下，可以提前追溯。
三：示例分析
题目来源于poj 3900The Robbery(类似于背包问题，但是不能够用背包求解)
1分析： w，c值较大，无法打开数组。 但是，由于发现n的值较小，(1 15 ) *15/2=120，因此也可以考虑进行dfs剪枝。
首先利用贪婪的想法重新排列箱子。 关键词是性价比(参考了poj的discuss )。 也就是说，单位重量价值最高的是第一位，检索时枚举顺序一定要注意从满到空。 这样，可以最快地找到可行的解，并利用它进行下一次剪枝。
-bottom:10px; padding-top:0px; padding-bottom:0px; border:0px; font-family:'Microsoft YaHei',微软雅黑,Arial,'Lucida Grande',Tahoma,sans-serif; line-height:24.0499992370605px">剪枝1. 之后所有的钻石价值+目前已经得到的价值<=ans 则剪枝。
剪枝2. 剩下的重量全部装目前最高性价比的钻石+目前已经得到的价值<=ans 则剪枝（非常重要的剪枝）。
2 程序代码
#include<cstdio>#include<cmath>#include<algorithm>using namespace std;#define MY_MAX(a,b) (a)>(b)?(a):(b)const int maxN = 20;struct NOTE{ long long weight; long long value; int num;}box[maxN];int n;// 个数小于20long long m,ans;// m 总重量,ans最优解long long sum[maxN]; //保存一个后缀和bool cmp(const struct NOTE &a, const struct NOTE &b){//按性价比排序,从大到小排列（注意若有取地址符号，则需有const） return a.value*1.0/a.weight > b.value*1.0/b.weight;}inline bool cut (int pos,long long now_value,long long last_weight){ if(pos == n+1) return true;//边界返回条件 if(now_value+sum[pos] < ans) return true;如果后面所有的钻石加起来都<=ans，剪掉 double best = (box[pos].value*1.0/box[pos].weight);//当前最大的性价比 if(now_value+(long long)ceil(best*last_weight) < ans) return true;//以这个性价比取剩下的所有重量，如果<=ans,剪掉 return false;}void dfs(int pos,long long now_value,long long last_weight) //pos 当前数组的下标位置，now_value 目前的重量和，last_weight当前背包剩余容量{ ans = MY_MAX(ans,now_value); if(cut(pos,now_value,last_weight)) return;//剪枝函数 for(int i=box[pos].num;i>=0;--i)//(暴力搜索)枚举顺序从满到空枚举，这样才能最快找到ans，然后利用ans剪枝 { if(last_weight<box[pos].weight*i) continue; dfs(pos+1,now_value+box[pos].value*i,last_weight-box[pos].weight*i); }}int main(){ int cas; long long sumv,sumw;// 价值和重量的和；仅仅用到了一次（特殊情况才用到，能够一次全带走） scanf("%d",&cas); while(cas--) { ans=0; sumv=sumw=0; scanf("%d%lld",&n,&m); for(int i=1;i<=n;i++) { scanf("%lld",&box[i].weight); sumw+=box[i].weight*i; } for(int i=1;i<=n;i++) { scanf("%lld",&box[i].value); box[i].num=i; sumv+=box[i].value*i; } // 以上是数据的输入，下面才是刚刚开始的 // 如果sumv开始就比m总重量还小，直接输出 if(sumw<=m) { printf("%lldn",sumv); continue; } sort(box+1,box+1+n,cmp);// 从1开始计数的 sum[n+1]=0; // 倒着开始的 for(int i=n;i>=1;i--) { //计算后缀和 sum[i]=sum[i+1]+box[i].value*box[i].num; } dfs(1,0,m); printf("%lldn",ans); } return 0;}