0-1背包问题指的是有一个能装w重的背包，和n个不同重量的物体，如何选择物体才能尽可能地装满背包。
回溯的处理思想，有点类似枚举搜索。我们枚举所有的解，找到满足期望的解。为了有规律地枚举所有可能的解，避免遗漏和重复，我们把问题求解的过程分为多个阶段。每个阶段，我们都会面对一个岔路口，我们先随意选一条路走，当发现这条路走不通的时候（不符合期望的解），就回退到上一个岔路口，另选一种走法继续走。
public int maxW = Integer.MIN_VALUE; //存储背包中物品总重量的最大值 // cw表示当前已经装进去的物品的重量和；i表示考察到哪个物品了； // w背包重量；items表示每个物品的重量；n表示物品个数 // 假设背包可承受重量100，物品个数10，物品重量存储在数组a中，那可以这样调用函数： // f(0, 0, a, 10, 100) public void f(int i, int cw, int[] items, int n, int w) { if (cw == w || i == n) { // cw==w表示装满了;i==n表示已经考察完所有的物品 if (cw > maxW) maxW = cw; return; } f(i+1, cw, items, n, w);//不选择放这个物体 f(i+1,cw + items[i], items, n, w);//选择放这个物体 }
这里还可以在优化一下，当cw+items[i]>w时就可以不用再递归了。
public int maxW = Integer.MIN_VALUE; //存储背包中物品总重量的最大值 // cw表示当前已经装进去的物品的重量和；i表示考察到哪个物品了； // w背包重量；items表示每个物品的重量；n表示物品个数 // 假设背包可承受重量100，物品个数10，物品重量存储在数组a中，那可以这样调用函数： // f(0, 0, a, 10, 100) public void f(int i, int cw, int[] items, int n, int w) { if (cw == w || i == n) { // cw==w表示装满了;i==n表示已经考察完所有的物品 if (cw > maxW) maxW = cw; return; } f(i+1, cw, items, n, w); if (cw + items[i] <= w) {// 已经超过可以背包承受的重量的时候，就不要再装了 f(i+1,cw + items[i], items, n, w); } }
原文：https://www.cnblogs.com/Sunqingyi/p/12679351.html