基本思路：要选择的物品有两种状态，选或者不选，很明显这是一个子集问题，所以递归部分参照子集模板修改，选了物品i就i+1,tw+w[i],tv+v[i]到下一层，不选就不变光i+1到下一层，然后每个子集（叶子节点）都比较得出的tv(价值)，最后得出最优解（最大价值）。
本文测试样例：
5 10 2 6 2 3 6 5 5 4 4 6输出样例：
15子集树：
递归（回溯）代码（含左孩子剪枝，易懂）：
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 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],tv+v[i],op); } op[i]=0; //不选取第i个物品 ，回溯 dfs(i+1,tw,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]; for(int i=1;i<=n;i++){ w[i]=in.nextInt(); v[i]=in.nextInt(); } dfs(1,0,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); } }
剪枝思路：
回溯剪枝代码： （该右孩子简剪枝方法适用于求装入背包的重量等于限制重量！）
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); } }
