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