做题的时候最后两个测试点超时我就剪枝了，不知道为什么耗时竟然更长了！？
题目：
给定n(n<=100)种物品和一个背包。物品i的重量是wi，价值为vi，背包的容量为C(C<=1000)。问:应如何选择装入背包中的物品，使得装入背包中物品的总价值最大? 在选择装入背包的物品时，对每种物品i只有两个选择：装入或不装入。不能将物品i装入多次，也不能只装入部分物品i。
输入格式:
共有n+1行输入： 第一行为n值和c值，表示n件物品和背包容量c； 接下来的n行，每行有两个数据，分别表示第i(1≤i≤n)件物品的重量和价值。
输出格式:
输出装入背包中物品的最大总价值。
输入样例:
在这里给出一组输入。例如：
5 10
2 6
2 3
6 5
5 4
4 6
输出样例:
在这里给出相应的输出。例如：
15
思路：
要选择的物品有两种状态，选或者不选，很明显这是一个子集问题，所以递归部分参照子集模板修改，选了物品i就i+1,tw+w[i],tv+v[i]到下一层，不选就不变光i+1到下一层，然后每个子集（叶子节点）都比较得出的tv(价值)，最后得出最优解（最大价值）。
剪枝思路：请戳这里
代码：
import java.util.*;
public class _01背包_剪枝 {
static int n,c;//物品数量和背包容量
static int[] w,v;//物品重量和物品价值
static int x[];//存放最优解
static int[] op;//存放临时解
static int maxv;//存放最优解的总价值
//i是数组起始位置，tw表示装入背包中的物品总重量，tv表示背包中物品的总价值
static void dfs(int i,int tw,int rw,int tv,int[] op){
if(i>n){ //找到一个叶子节点
if(tw<=c&&tv>maxv){ //找到一个满足条件的更优解，保存它
maxv=tv;
for(int j=1;j<=n;j++){
x[j]=op[j];
}
}
}
else{ //尚未找完所有物品
if(tw+w[i]<=c){ //左孩子节点剪枝：满足条件才放入第i个物品
op[i]=1; //选取第i个物品
dfs(i+1,tw+w[i],rw-w[i],tv+v[i],op);
}
if(tw+rw>=c){ //右孩子节点剪枝
op[i]=0; //不选取第i个物品 ，回溯
dfs(i+1,tw,rw-w[i],tv,op);
}
}
}
public static void main(String[] args) {
// TODO 自动生成的方法存根
Scanner in=new Scanner(System.in);
n=in.nextInt();
c=in.nextInt();
w=new int[n+1];
v=new int[n+1];
x=new int[n+1];
op=new int[n+1];
int sum=0;
for(int i=1;i<=n;i++){
w[i]=in.nextInt();
v[i]=in.nextInt();
sum+=w[i];
}
dfs(1,0,sum,0,op);
// System.out.println("最佳放入方案:");
// for(int i=1;i<=n;i++){
// if(x[i]==1){
// System.out.println(w[i]+" "+v[i]);
// }
// }
System.out.println(+maxv);
}
}
