0-1 背包问题的回溯实现技巧：

第 11 行的递归调用表示不选择当前物品，直接考虑下一个（第 i+1 个），故 cw 不更新

第 13 行的递归调用表示选择了当前物品，故考虑下一个时，cw 通过入参更新为 cw + items[i]

函数入口处的 if 分支表明递归结束条件，并保证 maxW 跟踪所有选择中的最大值

0-1背包问题根据老师下边这句话的讲解，代码再加两行注释就非常容易理解了

我们可以把物品依次排列，整个问题就分解为了 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); //当前物品不装进背包
  if (cw + items[i] <= w) {// 已经超过可以背包承受的重量的时候，就不要再装了
    f(i+1,cw + items[i], items, n, w); //当前物品装进背包
  }
}

0-1背包问题理解：
假设三个物品，每个物品在考虑时有两种选择，1-放进包，0-不放
11行代码表示不放进包里。13行代码表示放进包里。
三个物品遍历过程如下：
0 0 0 update maxW
0 0 1 update maxW
0 1 0 update maxW
0 1 1 update maxW
1 0 0 update maxW
1 0 1 update maxW
1 1 0 update maxW
1 1 1 update maxW

老师，你好，背包问题，貌似只记录了可以放进去的最大值，没有记录放进最大值对应的放法，我稍微
改了下，算出了最大值对应的所有放法，不知道可行不，希望老师回复下。
private int maxW = Integer.MIN_VALUE; // 存储背包中物品总重量的最大值
    // 下标表示物品序号，值表示是否放进背包:1放，0不放
    private int[] currentAnswer;
    //存储所有解(map key表示放进去的重量，value表示对应重量的物品放法)，
    //最终所有最优解为bestAnswerMap.get(maxW)
    private Map<Integer, List<int[]>> bestAnswerMap = new HashMap();

    // 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(currentAnswer == null){
            currentAnswer = new int[n];
        }

        if (cw == w || i == n) { // cw==w 表示装满了 ;i==n 表示已经考察完所有的物品
            if (cw >= maxW) {
                maxW = cw;
                int[] bestAnswer = new int[currentAnswer.length];
                for(int j=0; j<currentAnswer.length; j++){
                    bestAnswer[j] = currentAnswer[j];
                }
                if(bestAnswerMap.containsKey(cw)){
                    bestAnswerMap.get(cw).add(bestAnswer);
                }else{
                    List<int[]> list = new ArrayList<int[]>();
                    list.add(bestAnswer);
                    bestAnswerMap.put(cw, list);
                }
            }
            return;
        }
        currentAnswer[i] = 0;
        f(i+1, cw, items, n, w);
        if (cw + items[i] <= w) {// 已经超过可以背包承受的重量的时候，就不要再装了
            currentAnswer[i] = 1;
            f(i+1,cw + items[i], items, n, w);
        }
    }

最终maxW 对应的所有最优解为bestAnswerMap.get(maxW)

流程大概就是：
第一个不放，第二个不放，……，第n-1个不放，第n个不放。
第一个不放，第二个不放，……，第n-1个不放，
第n个放。
第一个不放，第二个不放， ……，第n-1个放，
第n个不放。
第一个不放，第二个不放， ……，第n-1个放，
第n个放。
……
以此类推
感觉这些问题就是将概率论知识转化成代码实现。

0-1背包python实现：
maxW = -1 # tracking the max weight

def backpack(i, cw, items, w):
    '''
    # i: the ith item, integer
    # cw: current weight, integer
    # items: python list of item weights
    # w: upper limit weight the backpack can load
    '''
    global maxW
    
    if cw==w or i==len(items): # base case
        if cw > maxW:
            maxW = cw
        return
    
    # There are 2 states, traverse both!!!
    backpack(i+1, cw, items, w) # do not choose
    if (cw + items[i] <= w):
        backpack(i+1, cw+items[i], items, w) # choose
    
# how to use
items = [2, 2, 4, 6, 3]
backpack(0, 0, items, 10)
print(maxW)