2023年8月1日发(作者：)

C++数据结构与算法分析——分⽀限界法（BFS求解01背包问题）分⽀限界法介绍分⽀限界，⼜叫分⽀定界，是⼀种系统搜索解空间的⽅法。它是的⼀种剪枝。在中我们已经知道，在DFS中有隐含的搜索树存在，BFS中同样也有(分析题⽬时⽤)分⽀限界，分为两个剪枝：分⽀和限界。1. 分⽀：即可⾏性剪枝，当遍历到⼀个点时，判断它是否符合题意，如果不符合，那么则将这个分⽀剪去。2. 限界：即最优性剪枝，这需要⼀个估价函数来判断当前遍历到的点是否有可能得到最优解，如果不可能得到最优解，那么该分⽀也可剪去。这么说也许有些抽象，当前我们选择01背包作为例⼦：题⽬描述有N件物品和⼀个容量是V的背包。每件物品只能使⽤⼀次。第i件物品的体积是vi，价值是wi。求解将哪些物品装⼊背包，可使这些物品的总体积不超过背包容量，且总价值最⼤。输出最⼤价值。输⼊格式第⼀⾏两个整数，N，V，⽤空格隔开，分别表⽰物品数量和背包容积。接下来有N⾏，每⾏两个整数vi,wi，⽤空格隔开，分别表⽰第i件物品的体积和价值。输出格式输出⼀个整数，表⽰最⼤价值。数据范围0V,那么之后所有选择中，只有对下件物品的选或不选两个选择，那么它的⼦树的总体积vtson>=vt>V恒成⽴，即可将其剪枝。经过可⾏性剪枝之后，以上框住的部分都将会被剪枝。为什么它叫可⾏性剪枝呢，因为它筛选的是连最简单的背包容量都会超过的选择⽅案，⽆论它的价值如何，我们都⽆法选择该⽅案，因为装不进背包，即该⽅案不可⾏。那么还能不能进⼀步剪枝呢？最优性剪枝(限界)最优性剪枝，表⽰在最优化问题中，若当前花费的代价已经超过了当前搜索的最优解，那么它⽆论如何都⽆法⽐当前最优解更优，可以直接停⽌对当前分⽀的搜索，即对当前⽅案树剪枝。限界，顾名思义，就是给定⼀个估价函数和⼀个界限，⼀旦该⽅案的估价函数值 > 界限值，那么将停⽌对当前分⽀的搜索，对当前⽅案树剪枝。那么如何设置估价函数呢？估价函数设计思路不唯⼀，但是要设计⼀个快准狠的估价函数却也并不简单，我们通过题⽬意思可以得到这样的信息：题⽬需要我们求的是价值最⼤的⽅案(假设已经进⾏过可⾏性剪枝，不存在超容量的选择⽅案，即每个⽅案都是合法的)。因此我们可以:1. 设计⼀个估价函数界限值res2. 在每个节点中都存⼀个值c表⽰当前⽅案的总价值，⼀个r表⽰之后可以获得的最⼤价值(剩余总价值),剩余总价值表⽰的是后⾯所有物品的价值之和，⽐如当前遍历第⼀件物品，那么它的剩余总价值就是后⾯三件物品的总价值。每遍历到⼀个点idx，我们都算⼀下它的r + c值，即当前总价值与剩余总价值之和，将之与当前最优解进⾏⽐较，如果r + c <= res，即意味着就算之后的物品它都选都⽆法超过最优解，即可将之剪枝，否则将它加⼊队列进⾏BFS。如果遍历到了解空间，那必然说明当前解的价值c > res，更新res。(图画不下了就不配图了)如此⼜可以剪枝⼀些⽅案树。在最优性剪枝的基础上我们能否继续进⾏优化呢？优化搜索顺序从最优性剪枝中，我们可以发现每个⽅案树的节点的估价函数值其实是不⼀样的，这就⼜带来了⼀个思考：在合法范围内，估价函数值越⼤的节点往下搜索得到最优解的可能应该是越⼤的，那么我们能否通过⼀些⼿段来优化搜索顺序呢？即让估价函数值越⼤的节点越提前搜索。其实是可⾏的。我们知道BFS是通过队列这个数据结构来完成的，它会⼀层⼀层往下拓展，那么我们只需要将队列改成优先队列，让估价函数值越⼤的节点⼊队后⾃动排到靠前位置，即可优化搜索顺序。代码#include #include #include #include using namespace std;const int N = (1 << 20) + 10;int n,m;int v[N],w[N];int res = -1;int s[N]; // s[i]存储的是从第1件物品到第i件物品的价值总和

struct good{ int idx,c,r,tv; // idx表⽰选法下标，c表⽰该选法的当前总价值，r表⽰当前选法的剩余总价值，tv表⽰该选法的当前总体积 bool operator > (const good& W) const{ return W.c + W.r > c + r; }}goods[N];int bfs(){ goods[1] = {1,0,0,0}; priority_queue,greater> q; (goods[1]); while(()){ auto t = ();// cout << << endl; (); int idx = << 1; goods[idx] = {idx,goods[].c,s[n] - s[(int)log2(idx)],goods[].tv}; goods[idx + 1] = {idx + 1,goods[].c + w[(int)log2(idx)],s[n] - s[(int)log2(idx)],goods[].tv + v[(int)log2(idx)]}; if((int)log2() == n) { //

假如已经是⼦节点，则更新答案 res = max(res,t.c); continue; } if(goods[idx].tv <= m && goods[idx].c + goods[idx].r > res) (goods[idx]); //

假如当前选法的总体积不超过背包容量，且当前价值+剩余价值 >

当前最优解，则装⼊背包 if(goods[idx + 1].tv <= m && goods[idx + 1].c + goods[idx + 1].r > res) (goods[idx + 1]); } return res;}int main(){ cin >> n >> m; for(int i = 1; i <= n; i ++) cin >> v[i] >> w[i],s[i] = s[i - 1] + w[i];//// for(int i = 2; i < 1 << n + 1; i ++){// goods[i] = {i,goods[i >> 1].c + (i&1)*w[(int)log2(i)],s[n] - s[(int)log2(i)],goods[i >> 1].tv + (i&1)*v[(int)log2(i)]};// }//// for(int i = 1; i < 1 << n + 1; i ++) printf("i = %d,c[i] = %d,r[i] = %d,tv[i] = %dn",goods[i].idx,goods[i].c,goods[i].r,goods[i].tv); cout << bfs() << endl; return 0;}运⾏截图

2023年8月1日发(作者：)

C++数据结构与算法分析——分⽀限界法（BFS求解01背包问题）分⽀限界法介绍分⽀限界，⼜叫分⽀定界，是⼀种系统搜索解空间的⽅法。它是的⼀种剪枝。在中我们已经知道，在DFS中有隐含的搜索树存在，BFS中同样也有(分析题⽬时⽤)分⽀限界，分为两个剪枝：分⽀和限界。1. 分⽀：即可⾏性剪枝，当遍历到⼀个点时，判断它是否符合题意，如果不符合，那么则将这个分⽀剪去。2. 限界：即最优性剪枝，这需要⼀个估价函数来判断当前遍历到的点是否有可能得到最优解，如果不可能得到最优解，那么该分⽀也可剪去。这么说也许有些抽象，当前我们选择01背包作为例⼦：题⽬描述有N件物品和⼀个容量是V的背包。每件物品只能使⽤⼀次。第i件物品的体积是vi，价值是wi。求解将哪些物品装⼊背包，可使这些物品的总体积不超过背包容量，且总价值最⼤。输出最⼤价值。输⼊格式第⼀⾏两个整数，N，V，⽤空格隔开，分别表⽰物品数量和背包容积。接下来有N⾏，每⾏两个整数vi,wi，⽤空格隔开，分别表⽰第i件物品的体积和价值。输出格式输出⼀个整数，表⽰最⼤价值。数据范围0V,那么之后所有选择中，只有对下件物品的选或不选两个选择，那么它的⼦树的总体积vtson>=vt>V恒成⽴，即可将其剪枝。经过可⾏性剪枝之后，以上框住的部分都将会被剪枝。为什么它叫可⾏性剪枝呢，因为它筛选的是连最简单的背包容量都会超过的选择⽅案，⽆论它的价值如何，我们都⽆法选择该⽅案，因为装不进背包，即该⽅案不可⾏。那么还能不能进⼀步剪枝呢？最优性剪枝(限界)最优性剪枝，表⽰在最优化问题中，若当前花费的代价已经超过了当前搜索的最优解，那么它⽆论如何都⽆法⽐当前最优解更优，可以直接停⽌对当前分⽀的搜索，即对当前⽅案树剪枝。限界，顾名思义，就是给定⼀个估价函数和⼀个界限，⼀旦该⽅案的估价函数值 > 界限值，那么将停⽌对当前分⽀的搜索，对当前⽅案树剪枝。那么如何设置估价函数呢？估价函数设计思路不唯⼀，但是要设计⼀个快准狠的估价函数却也并不简单，我们通过题⽬意思可以得到这样的信息：题⽬需要我们求的是价值最⼤的⽅案(假设已经进⾏过可⾏性剪枝，不存在超容量的选择⽅案，即每个⽅案都是合法的)。因此我们可以:1. 设计⼀个估价函数界限值res2. 在每个节点中都存⼀个值c表⽰当前⽅案的总价值，⼀个r表⽰之后可以获得的最⼤价值(剩余总价值),剩余总价值表⽰的是后⾯所有物品的价值之和，⽐如当前遍历第⼀件物品，那么它的剩余总价值就是后⾯三件物品的总价值。每遍历到⼀个点idx，我们都算⼀下它的r + c值，即当前总价值与剩余总价值之和，将之与当前最优解进⾏⽐较，如果r + c <= res，即意味着就算之后的物品它都选都⽆法超过最优解，即可将之剪枝，否则将它加⼊队列进⾏BFS。如果遍历到了解空间，那必然说明当前解的价值c > res，更新res。(图画不下了就不配图了)如此⼜可以剪枝⼀些⽅案树。在最优性剪枝的基础上我们能否继续进⾏优化呢？优化搜索顺序从最优性剪枝中，我们可以发现每个⽅案树的节点的估价函数值其实是不⼀样的，这就⼜带来了⼀个思考：在合法范围内，估价函数值越⼤的节点往下搜索得到最优解的可能应该是越⼤的，那么我们能否通过⼀些⼿段来优化搜索顺序呢？即让估价函数值越⼤的节点越提前搜索。其实是可⾏的。我们知道BFS是通过队列这个数据结构来完成的，它会⼀层⼀层往下拓展，那么我们只需要将队列改成优先队列，让估价函数值越⼤的节点⼊队后⾃动排到靠前位置，即可优化搜索顺序。代码#include #include #include #include using namespace std;const int N = (1 << 20) + 10;int n,m;int v[N],w[N];int res = -1;int s[N]; // s[i]存储的是从第1件物品到第i件物品的价值总和

struct good{ int idx,c,r,tv; // idx表⽰选法下标，c表⽰该选法的当前总价值，r表⽰当前选法的剩余总价值，tv表⽰该选法的当前总体积 bool operator > (const good& W) const{ return W.c + W.r > c + r; }}goods[N];int bfs(){ goods[1] = {1,0,0,0}; priority_queue,greater> q; (goods[1]); while(()){ auto t = ();// cout << << endl; (); int idx = << 1; goods[idx] = {idx,goods[].c,s[n] - s[(int)log2(idx)],goods[].tv}; goods[idx + 1] = {idx + 1,goods[].c + w[(int)log2(idx)],s[n] - s[(int)log2(idx)],goods[].tv + v[(int)log2(idx)]}; if((int)log2() == n) { //

假如已经是⼦节点，则更新答案 res = max(res,t.c); continue; } if(goods[idx].tv <= m && goods[idx].c + goods[idx].r > res) (goods[idx]); //

假如当前选法的总体积不超过背包容量，且当前价值+剩余价值 >

当前最优解，则装⼊背包 if(goods[idx + 1].tv <= m && goods[idx + 1].c + goods[idx + 1].r > res) (goods[idx + 1]); } return res;}int main(){ cin >> n >> m; for(int i = 1; i <= n; i ++) cin >> v[i] >> w[i],s[i] = s[i - 1] + w[i];//// for(int i = 2; i < 1 << n + 1; i ++){// goods[i] = {i,goods[i >> 1].c + (i&1)*w[(int)log2(i)],s[n] - s[(int)log2(i)],goods[i >> 1].tv + (i&1)*v[(int)log2(i)]};// }//// for(int i = 1; i < 1 << n + 1; i ++) printf("i = %d,c[i] = %d,r[i] = %d,tv[i] = %dn",goods[i].idx,goods[i].c,goods[i].r,goods[i].tv); cout << bfs() << endl; return 0;}运⾏截图