通过“01背包”问题理解深搜、剪枝、回溯以及递归优化
背包问题是我们的老朋友了，在学习贪心算法时，我们接触到的 是“可分割”的背包问题，传送门：《深入理解贪心算法》 文章末尾我提到了如果物品不能分割，那就是 01 背包问题，01 背包问题是不能用贪心算法来解决的。01 背包也有很多种版本，
这次我们来解决一个最简单的版本：背包总承重为 w，有 n 个物 体，每个物体重量不等，同时不可分割，如何在不超过背包总重 量的前提下，让放入背包中的物品总重量最大？ 本次我们要使用回溯算法来解决这个问题。 对于每个物品来说都有装与不装两种情况，所以总的方案共有 2 的 n 次方。计算出这 2 的 n 次方种情况的结果，对结果进行判 定，就能得到最终的结果。对所有可能的情况不重不漏地访问一 遍，虽然不存在明确的图的结构，但其实我们是在一个抽象的结 果集中进行广义的“深度优先搜索”
#include <bits/stdc++.h>
using namespace std;
int items[] = {2,2,4,6,3};
int n =5,w=9;
int maxW = 0; // 存储背包中物品总重量的最大值
// cw 表示当前已经装进去的物品的重量和；i 表示考察到哪个物品
了；
void dfs(int i,int cw) {
if (i == n) { //撞到了南墙，得到了n个物品的一种可能性
if (cw <= w && cw > maxW) maxW = cw;
return;
}
//先考察不把第i个物品放入背包的情况
dfs(i+1, cw);
//再考察把第i个物品放入背包的情况
dfs(i+1,cw + items[i]);
}
int main()
{
dfs(0,0);
cout<<maxW;
return 0;
}
回溯算法是什么呢？引用百度百科中“回溯算法”的词条： 回溯算法实际上是一个类似枚举的搜索尝试过程，主要是在搜索 尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回 溯”返回，尝试别的路径。 回溯算法的诞生要远远早于计算机的历史，回溯算法的经典场景 “8皇后问题”是国际西洋棋棋手马克斯·贝瑟尔于1848年提出的。 深度优先搜索重于检查所有情况，有时候我们不需要遍历完所有 的情况，因为很多情况中搜索到某一阶段的时候已经不满足题目 的条件了，完全没有必要继续浪费时间，此时提前结束，称之为 “剪枝”。深度优先搜素中加入剪枝之后，就符合“回溯算法”的定 义了。下面是使用剪枝优化后的 01 背包解法：
#include <bits/stdc++.h>
using namespace std;
int items[] = {2,2,4,6,3};
int n =5,w=9;
int maxW = 0; // 存储背包中物品总重量的最大值
// cw 表示当前已经装进去的物品的重量和；i 表示考察到哪个物品
了；
void dfs(int i,int cw) {
if (cw == w || i == n) { // cw==w 表示装满了 ;i==n 表示已
经考察完所有的物品
if (cw > maxW) maxW = cw;
return;
}
//先考察不把第i个物品放入背包的情况
dfs(i+1, cw);
//再考察放入背包的情况。
//这里是一个剪枝过程，如果第i个物品放进去超过背包体积了，
那压根不把它放进去
if (cw + items[i] <= w) {
//背包容量不满，可以继续装
dfs(i+1,cw + items[i]);
}
}
int main()
{
dfs(0,0);
cout<<maxW;
return 0;
}
剪枝之后的算法提速了不少，但是还有一个问题没有克服，那就 是重复计算的问题，我们继续画出递归树分析一下：
相信你已经发现了，递归计算中出现了重复计算的情况，为了减 少重复计算，你可以每次计算完之后都把结果暂存起来，dfs每次 计算时先看看暂存的结果
#include <bits/stdc++.h>
using namespace std;
int items[] = {2,2,4,6,3};
bool mem[5][10];//计算过的结果标注
int n =5,w=9;
int maxW = 0; // 存储背包中物品总重量的最大值
// cw 表示当前已经装进去的物品的重量和；i 表示考察到哪个物品
了；
void dfs(int i,int cw) {
if (cw == w || i == n) { // cw==w 表示装满了 ;i==n 表示已
经考察完所有的物品
if (cw > maxW) maxW = cw;
return;
}
if (mem[i][cw]) return ;//重复计算，直接返回
mem[i][cw] = true;//第一次计算
dfs(i+1, cw);
if (cw + items[i] <= w) {
//背包容量不满，可以继续装
dfs(i+1,cw + items[i]);
}
}
int main()
{
dfs(0,0);
cout<<maxW;
return 0;
}
优化之后的回溯解法其实效率已经非常高了，希望你能在不断优 化中掌握递归相关的思想，后面我们还会学习背包问题的终极解 法：动态规划。