用回溯算法求解0-1背包问题

打个比喻，我们的人生会面临无数的选择，我们每次选择的时候都会选择自己任务的最优解，但最终的结果并不一定是最优解，可能面临抉择的选择了贪图小利，最终一生碌碌无为。上面求最优解的方式就是贪心算法，为什么这时候贪心算法不好用了，就是因为我们的每次选择都是有关联的，我们的这次决定会影响我们今后的选择。所以这时候贪心算法不好用了，那么如果我们能吃后悔药，回头看看我们可选择的所有情况，然后就可以从所有情况中选择最优解。这就是回溯算法思想。

0-1背包问题。

我们有一个背包，最大的装载量为W，有n个重量不一样的物体，且物体不可分割，求背包能装载的最大重量。代码如下

int maxW = 0;

/**
 0-1背包问题

 @param i 当前遍历到的位置
 @param cw 当前书包总重量
 @param items 物品重量集合
 @param n 总物品的数量
 @param w 书包可以承受的最大重量
 */
void f(int i, int cw, int* items, int n, int w){
//    printf("i:%d cw:%d\n",i,cw);
    //终止条件，当前物品总质量等于背包可以承受的最大质量
    if (cw == w || i == n){
        //更新背包可以承受的最大质量
        printf("i:%d cw:%d\n",i,cw);
        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);
    }
}
int main(int argc, const char * argv[]) {
    int a[8] = {23,12,2,56,121,33,5,1};
    f(0, 0, a, 8, 100);
    printf("最大质量：%d",maxW);
    // insert code here...
    printf("Hello, World!\n");
    return 0;
}

代码很见到，但是理解起来有点困难，首先我们的思路是枚举所有的情况，并且排除超重情况、
或许先把判断去掉更好理解一点，一个物品就两种情况装或者不装，遍历所有情况，更新最大值。

if (i == n){
    if (cw > maxW) maxW = cw;
return;
}
f(i+1, cw, items, n, w);
f(i+1, cw+items[i], items, n, w);

判断是为了去除超重情况，然后加上判断再理解一下。