devbox
盐析白兔
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

五种基础算法小结与典型题目分享（动态规划、分治、贪心、回溯、分支限界）

作者：盐析白兔 | 2024-02-26 21:51:13

赞

踩

五种基础算法小结与典型题目分享（动态规划、分治、贪心、回溯、分支限界）

动态规划算法小结

基本思想

动态规划是用于解决多阶段决策问题的算法策略。它通过用变量集合描述当前情境来定义“状态”，进而用这些状态表达每个阶段的决策。

每个阶段的状态是基于前面的状态经过某种决策得到的。通过建立状态间的递推关系，并将其形式化为数学递推式，得到“状态转移方程”。

适用条件

适用动态规划的问题必须满足最优化原理和无后效性。

· 最优化原理：一个最优化策略具有这样的性质：不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。

·无后效性：将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结，即满足无环递推关系和历史独立性。

·子问题的重叠性：动态规划算法的关键在于解决冗余，这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术，它在实现的过程中，不得不存储产生过程中的各种状态，所以它的空间复杂度要大于其他的算法。选择动态规划算法是因为动态规划算法在空间上可以承受，而搜索算法在时间上却无法承受，所以我们舍空间而取时间。

问题图谱

在使用动态规划算法时，需要基于描述的问题，将状态合理定义，并将已知的基准或边界初始化；再给出状态转移方程，这样就可以求出后续中间状态，并提取目标答案。

以下为例题：

题目1：字符串最小编辑距离

给定两个字符串A和B，你的任务是计算将A转换为B所需的最少操作数。你可以进行以下三种操作：

（1）删除A中的一个字符。

（2）向A中插入一个字符。

（3）替换A中的一个字符为另一个字符。

请你计算将 A 转换为 B 所需的最小操作数。（输入内容为四行，分别为A、B的字符串字数以及对应的内容，输出一个整数，表示从A转换到B所需的最小操作数）

个人分析思路：可以使用二维DP的思路去处理，用二维数组dp[i][j]表示A中前i个字符编辑到B中前j个字符的最短编辑距离。这样A或B每增加一个字符，最小编辑距离相比于矩阵相邻的更小规模问题都是多一次编辑，这样可以筛选出最小值。

参考代码：

  1. #include<iostream>
  2. #include<string>
  3. #include<algorithm>
  4. using namespace std;
  5. int n, m;//表示A和B的字符数
  6. int main(){
  7.     string a,b;
  8.     cin >> n >> a >> m >> b;
  9.     int i, j, dp[n+1][m+1];
  10.     //初始化二维数组
  11.     for(i=0;i<=n;i++) dp[i][0] = i;
  12.     for(j=0;j<=m;j++) dp[0][j] =j;
  13.     //状态转移方程
  14.     for(i=1;i<=n;i++){
  15.         for(j=1;j<=m;j++){
  16.             if(a[i]==b[j]) dp[i][j]=dp[i-1][j-1];
  17.             else
  18.                 dp[i][j]=min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])+1;
  19.         }
  20.     }
  21.     cout << dp[n][m] << endl;
  22.     return 0;
  23. }

 

题目2：金币合并

你有N（N<=300）堆金币排成一行。每堆金币有一定的重量，用整数数组表示。你需要通过一系列操作将所有金币合并成一堆。在每次操作中，你可以选择相邻的两堆金币进行合并。合并的代价为这两堆金币的重量之和，合并后新的一堆金币的重量也为这两堆金币的重量之和。由于合并的顺序不同，最终的合并代价也会不同。你的任务是找到一种合并顺序，使得合并所有金币的总代价最小，并输出这个最小的合并代价。（输入两行内容为金币堆数与N个整数表示每堆金币的重量，输出一个整数表示合并最小代价）

个人分析思路：该题目是区间类型的DP问题，需要二维数组解决，在计算区间内最小合并成本时，需要考虑区间可能分成的任意两部分的合并成本。

参考代码：

  1. #include<iostream>
  2. #include<algorithm>
  3. using namespace std;
  4. int dp[310][310];//直接定义dp数组
  5. int a[310], s[310];//s数组记录前缀和
  6.  
  7. int main() {
  8.     int n;
  9.     cin >> n;
  10.     for(int i = 1; i <= n; i++) {
  11.         cin >> a[i];
  12.         s[i] = s[i - 1] + a[i];
  13.     }
  14.     //状态转移方程
  15.     for(int len = 2; len <= n; len++) {
  16.         for(int l = 1; l+len-1 <= n; l++) {
  17.             int r = l+len-1;
  18.             dp[l][r] = 2e9;
  19.             for(int k = l; k < r; k++)
  20.                 dp[l][r] = min(dp[l][r], dp[l][k] + dp[k+1][r] + (s[r] - s[l-1]));
  21.         }
  22.     }
  23.     cout << dp[1][n] << endl;
  24.     return 0;
  25. }

 

题目3：股票交易（含冷冻期）

你是一位股票交易员，你现在有一些股票的价格列表，其中第i天的股票价格是prices[i]。设计一个算法来找到获取最大利润的交易策略。交易规则如下：

·你可以进行多次交易，但是必须在再次购买前卖出股票。

·卖出股票后，不能在次日立即买入，必须等待至少一天。

输入两行，第一行为天数（小于500），第二行为一个数组表示每天股票价格，请返回你能获得的最大利润。

个人分析思路：股票的各种问题及变形是算法类题目中常见类型，这里限制连续交易的时间是需要考虑到每天有持有股票和不持有两种状态，因此dp数组需要两个维度，表示股票持有状态的行数只需要两行。

参考代码：

  1. #include<iostream>
  2. #include<algorithm>
  3. using namespace std;
  4. int dp[500][2];//直接定义dp数组
  5. int w[510];
  6.  
  7. int main() {
  8.     int n;
  9.     cin >> n;
  10.     for(int i = 1; i<=n; i++)
  11.         cin >> a[i];
  12.     f[0][0]=0; f[0][1]=-1e6; //初始化
  13.     //状态转移方程
  14.     for(int i=1; i<=n; ++i){
  15.         f[i][0]=max(f[i-1][0],f[i-1][1]+w[i]);    
  16.         f[i][1]=max(f[i-1][1],f[i-1][0]-w[i]);
  17.     }
  18.     cout << f[n][0] << endl;
  19.     return 0;
  20. }

 

分治算法小结

基本思想

分治策略（Divide and Conquer）的基本思想是将一个复杂的问题分解成两个或更多个相同或相似的子问题，直至这些子问题可以简单地直接求解。求解子问题后，再将子问题的解组合起来得到原问题的解。

基本步骤与注意事项

分治法一般的解决步骤为：分解-解决-合并。在使用分治策略时，一般要注意以下事项：

·确保子问题与原问题相似：为了能够使用分治策略，子问题应该是原问题的更小规模的同类问题。

·子问题之间应当独立：最好确保子问题是相互独立的，这样它们可以独立地、甚至可能并行地被解决。

·考虑分治的开销：在每一步中分解问题和合并结果都会产生一定的开销。当子问题的规模减少到一定程度时，分治的开销可能超过直接解决问题的开销。因此，对于足够小的子问题，通常使用简单方法直接解决而不再继续分解。

问题图谱

题目1：求逆序对数量

输入第一行为整数n, 代表数列中元素个数，第二行包含n个整数，表示数列的元素，元素之间由一个空格分隔。计算出数列中逆序对数总数，逆序对定义为数列中一对元素(a[i], a[j])，其中i < j且a[i] > a[j]。

个人分析思路：在分治的递归过程中，只需要合并左半部分的逆序对、右半部分的逆序对，跨越中间点的逆序对。

参考代码：

  1. #include <iostream>
  2. using namespace std;
  3. const int N = 100010;
  4. int n;
  5. int a[N], tmp[N];
  6.  
  7. long long merge_sort(int l, int r){ //基于归并排序的原理
  8.     if( l >= r) return 0;
  9.     long long ans = 0;
  10.     int mid = (l + r) >> 1;
  11.     ans = merge_sort(l, mid) + merge_sort(mid+1, r);
  12.  
  13.     int k=0, i=l, j=mid+1;
  14.     while(i <= mid && j <= r){
  15.         if(a[i] <= a[j]) tmp[k++] = a[i++];
  16.         else{
  17.             tmp[k++] = a[j++];
  18.             ans += mid - i + 1; //第一个里面的i后面的所有 
  19.         }
  20.     }
  21.     //归并排序原理处理另一部分
  22.     while(i <= mid) tmp[k++] = a[i++];
  23.     while(j <= r) tmp[k++] = a[j++];
  24.     for(int i=l,k=0; i <= r; i++, k++) a[i] = tmp[k];
  25.     return ans;
  26. }
  27.  
  28. int main(){
  29.     cin >> n;
  30.     for(int i = 0; i < n; i++) cin >> a[i];
  31.     cout << merge_sort(0, n-1) << endl;
  32.     return 0;
  33. }

 

题目2：最大连续子数组和

第一行输入数组长度n，第二行输入该整数数组，元素之间间隔一个空格。找出其中的连续子数组（至少包含一个元素）使得该子数组的和最大，并返回这个最大的和，用一个整数输出。

个人分析思路：同上题，也是递归计算左右子区间最大子序，通过计算横跨中间的最大子序和LR，这涉及从中间向左扫描求左半边最大值，以及从中间向右扫描求右半边最大值，最后相加。

参考代码：

  1. #include <iostream>
  2. using namespace std;
  3. int a[1010];
  4.  
  5. int fun(int l, int r){ // 求横跨左右的最大字段和
  6.     int m = (l + r)/2;
  7.     int sumL = 0, ansL = a[m];
  8.     int sumR = 0, ansR = a[m+1];
  9.     for(int i=m; i >=l; i--){
  10.         sumL += a[i];
  11.         ansL = max(ansL,sumL);
  12.     }
  13.     for(int i=m+1; i <=r; i++){
  14.         sumR += a[i];
  15.         ansR = max(ansR,sumR);
  16.     }
  17.     return ansL+ansR;
  18. }
  19. int max_sum(int l, int r){  
  20.     if(l==r) return a[l];
  21.     int m = (l+r)/2;
  22.     int L = max_sum(l,m);
  23.     int R = max_sum(m+1,r);
  24.     int LR = fun(l,r);
  25.     return max(max(L,R),LR);
  26. }
  27.  
  28. int main(){
  29.     int n;
  30.     cin >> n;
  31.     for(int i = 1; i <= n; i++)
  32.         cin >> a[i];
  33.     cout << max_sum(1,n);
  34.     return 0;
  35. }

题目3：数列分段

对于一个长度为N的正整数数列，现要将其分成M段（M ≤ N），要求每段连续，并使每段的和的最大值尽可能小。第一行输入正整数N、M。第二行包含N个由空格隔开的非负整数，表示数列中的每个元素。输出一个正整数，表示分段后每段和的最大值的最小可能值。

个人分析思路：与上面题相似，使用二分思想，每次在可行区间内取中点求解。设置一个检查函数，在可行的范围尽量缩小，利用二分的方式缩短查找进程，直至得到最优解。

参考代码：

  1. #include <iostream>
  2. using namespace std;
  3. int a[100010];
  4. int n, m;
  5.  
  6. bool check(long long k){
  7.     int cnt = 1; //需要初始化为1，最少有1段 
  8.     int sum = 0;
  9.     for(int i = 1; i <= n; i++){
  10.         if( a[i] > k) return false;
  11.         if(sum + a[i] > k){
  12.             cnt++;
  13.             sum = a[i];
  14.         }else{
  15.             sum += a[i];
  16.         }
  17.     }
  18.     return cnt <= m;  //满足题目要求，需要再减少试试 
  19. }
  20.  
  21. int main(){
  22.     cin >> n >> m;
  23.     long long l = 0, r = 0;
  24.     for(int i = 1; i <= n; i++){
  25.         cin >> a[i]; 
  26.         if(a[i] > l) l = a[i];
  27.         r += a[i];
  28.     }
  29.     long long ans = 0;
  30.     while(l <= r){
  31.         long long mid = (r + l) / 2 ;
  32.         if(check(mid)){
  33.             ans = mid;
  34.             r = mid - 1; 
  35.         }else{
  36.             l = mid + 1;
  37.         }
  38.     }
  39.     cout << ans << endl;
  40.     return 0;
  41. }

 

贪心算法小结

基本思想

贪心算法（Greedy Algorithm，又称贪婪算法）是指：在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择。在我们的常识中，有时候也会基于贪心思想来思考问题。

贪心算法可以解决的问题范畴也很广，严格证明的话一般使用数学方法中的数学归纳法和反证法。

贪心算法步骤与特性

贪心算法一般按如下步骤进行：

·建立数学模型来描述问题。

·把求解的问题分成若干个子问题。

·对每个子问题求解，得到子问题的局部最优解。

·把子问题的解局部最优解合成原来问题的一个解。

问题图谱

题目1：部分背包问题

阿里巴巴遇到了一个挑战，他发现了一个装满金币的洞穴。洞穴里有N堆金币（N 不超过 100），每堆金币的重量和价值分别为mi和vi，其中mi和vi 的值均不超过100。他有一个背包，它的最大承重为T（T不超过1000），但他可能无法装下所有的金币。每堆金币都可以任意切割成更小的部分，且切割后的金币保持原来的重量价值比不变。问题是，阿里巴巴最多能带走多少价值的金币？输入第一行包含两个整数N和T。接下来N行，每行包含两个整数mi和vi。

个人分析思路：计算每堆金币的单位价值-按单位价值排序-选择金币-计算总价值。通过每一步选择当前最优的决策（即单位价值最高的金币）来找到问题的一个有效解。

参考代码：

  1. #include <iostream>
  2. #include <algorithm>
  3. using namespace std;
  4.  
  5. struct node {
  6.     int m, v;
  7.     double p;
  8. };
  9.  
  10. node a[105];
  11.  
  12. bool cmp(node a, node b) {
  13.     return a.p > b.p;
  14. }
  15.  
  16. int main() {
  17.     int n, t;
  18.     cin >> n >> t;
  19.     //求单位价值
  20.     for (int i = 1; i <= n; i++) {
  21.         cin >> a[i].m >> a[i].v;
  22.         a[i].p = 1.0 * a[i].v / a[i].m;
  23.     }
  24.     //结构体排序
  25.     sort(a + 1, a + 1 + n, cmp);
  26.     double  ans = 0;
  27.     for (int i = 1; i <= n ; i++) {
  28.         if (t >= a[i].m) {
  29.             ans += a[i].v;
  30.             t -= a[i].m;
  31.         } else {
  32.             ans += a[i].p * t;
  33.             break;
  34.         }
  35.     }
  36.     cout << ans << endl;
  37.     return 0;
  38. }

 

题目2：股票交易（基础，无冷冻）

内容与之前基本一致，每次股价上升都考虑进去。

参考代码：

  1. #include<iostream>
  2. using namespace std;
  3.  
  4. const int N = 100010;
  5. int n;
  6. int a[N];
  7.  
  8. int main(){
  9.     cin >> n;
  10.     for(int i = 1; i <= n; i++) cin >> a[i];
  11.     int ans = 0;
  12.     for(int i = 1; i < n; i++)
  13.     {
  14.         if(a[i] < a[i+1]) ans += a[i+1] - a[i]; 
  15.     }
  16.     cout << ans << endl;
  17.     return 0;
  18. }

 

题目3：均分图书

在学校图书馆，管理员小明正在整理一些图书。这些图书被分成了n堆，编号分别为 1, 2, ..., n。每堆上有若干本书，但图书的总数必为n的倍数。小明可以在任一堆上取若干本图书，然后移动它们。

移动图书的规则为：

·在编号为 1 的堆上取的图书，只能移到编号为 2 的堆上；

·在编号为 n 的堆上取的图书，只能移到编号为 n-1 的堆上；

·在其他编号的堆上取的图书，可以移到相邻左边或右边的堆上。

现在要求你帮助小明找出一种移动方法，用最少的移动次数使每堆上图书的数量都一样多。第一行输入一个整数 n (1 <= n <= 100)，表示图书堆的数量。第二行输入 n 个整数 a_1, a_2, ... , a_n(1 <= a_i <= 1e5)，用空格隔开，表示每堆图书初始时的数量。保证图书总数是 n 的倍数。

解析思路：为了达到最快的平衡，每一步都应尽量使当前堆与平均数接近。从第一堆开始，我们看它与平均值的差异，并将这个差值的图书移到第二堆，以此类推，直到最后一堆。每移动一次，都记录移动的次数，最后输出总的移动次数。

参考代码：

  1. #include <iostream>
  2. using namespace std;
  3. int main()
  4. {
  5.     int a[101],n,d=0; //d表示平均数 
  6.     float sum=0,c=0; // sum表示平均数 c用来求和 
  7.     cin>>n;
  8.     for(int i=0;i<n;i++)
  9.     {
  10.         cin >> a[i];
  11.         c = c+a[i]; //计算和 
  12.     }
  13.     sum=c/n; //计算平均数 
  14.     for(int i=0;i<n;i++)
  15.     {
  16.         if(a[i]!=sum) //判断一下是否等于平均数，如果等于就直接下一次。 
  17.         {
  18.             a[i+1] = a[i+1]+(a[i]-sum); //移动图书 
  19.             a[i] = sum; //移动过后就变成了平均数 
  20.             d++; //移动次数增加一次 
  21.         }
  22.     }
  23.     cout << d << endl;
  24.     return 0;
  25. }

 

回溯算法小结

基本思想

回溯法是一种通过递归方式来解决问题的算法框架，它试图通过探索所有可能的解决方案来找到问题的解。这种方法通常用于解决组合问题、划分问题、子集问题、排列问题和棋盘问题等。在解决这些问题时，回溯算法会形成一棵决策树来表示求解过程。

基本步骤

针对所给问题，定义问题的解空间，它至少包含问题的一个（最优）解，并确定易于搜索的解空间结构。然后：从列表中选择-递归-撤销（回溯）。

问题图谱

题目1：编写一个程序，用于枚举 n 个数 x1, x2, ..., xn 的所有排列方式（即全排列枚举）。如果两种排列方式的前k-1个数相同，则将第k个数序号更小的排列放在前面。例如，当n=3且 x={100, 20, 5} 时，应该按以下顺序输出结果：{100, 20, 5}, {100, 5, 20}, {20, 100, 5}, {20, 5, 100}, {5, 100, 20}, {5, 20, 100}。

输入第一行为整数n, 第二行为这些正整数；输出每个排列为一行。

题目分析：每次按顺序选择数组元素，生成解空间数，顺序输出即可。

参考代码：

  1. #include<iostream>
  2. #include<algorithm>
  3. using namespace std;
  4.  
  5. int n;
  6. bool a[30];
  7. int b[30], x[30];
  8.  
  9. void print()
  10. {
  11.     for(int i = 1; i <= n; i++)
  12.         cout << x[b[i]] << ' ';
  13.     cout << endl;
  14. }
  15.  
  16. void dfs(int step)
  17. {
  18.     if (step > n)
  19.     {
  20.         print();
  21.         return;
  22.     }
  23.     for (int i = 1; i <= n; i++)
  24.     {
  25.         if (a[i]) continue; // 判断是否使用过 
  26.         a[i] = true;        // 标记使用 
  27.         b[step] = i;        // 记录下该值的下标 
  28.         dfs(step + 1);     //继续搜索
  29.         a[i] = false;       // 还原
  30.     }
  31. }
  32.  
  33. int main() 
  34. {
  35.     cin >> n;
  36.     for(int i = 1; i <= n; i++)
  37.         cin >> x[i];
  38.     dfs(1);
  39.     return 0;
  40. }

 

题目2：略微不同的n皇后

在一个n×n的国际象棋棋盘上，需要放置n个皇后，使得每一行、每一列以及每条对角线上最多只有一个皇后。这就构成了n皇后问题。例如，当n=8 时，八皇后问题就是在 8×8 的棋盘上放置八个皇后，遵循上述规则。你的任务是根据给定的n，输出n皇后问题的前k个解。由于每一行必定只有一个皇后，如果两个解的前k-1行的皇后位置相同，那么在第k行中皇后位置更靠左的解应排在前面（即按字典序排序）。

解析思路：同上个问题，每行选取哪个格子作为检索解空间树的第一层，依次类推，通过要求构建剪枝函数，当不满足要求或求到符合要求的解时回溯。

参考代码：

  1. #include<iostream>
  2. #include<algorithm>
  3. using namespace std;
  4.  
  5. int n, k;
  6. int cnt; //记录已经求到第几个答案 
  7. int a[20]; //记录每行皇后放的位置 
  8.  
  9. bool flag1[20];
  10. bool flag2[40]; 
  11. bool flag3[40];
  12. // flag1[j]表示第j列有没有皇后
  13. // flag2[i + j]表示行列和为i+j有没有皇后
  14. // flag3[i - j + n]表示行列差为i-j+n有没有皇后
  15.  
  16. // 排列树 
  17. void dfs(int step) // step代表第几行 
  18. {
  19.     if(step > n) { // 找到一个可行解后，打印 
  20.         if(cnt++ == k) exit(0); //超过了k
  21.         // 打印一组可行解 
  22.         for(int i = 1; i <= n; i++) 
  23.             cout << a[i]  << " ";
  24.         cout << endl; 
  25.     }
  26.  
  27.     // 每行挨个位置尝试  1 ~ n 
  28.     for(int y = 1 ; y <= n; y++){
  29.         // 如果step行第y个位置冲突，则剪枝
  30.         int x = step;
  31.  
  32.         if(flag1[y] || flag2[x + y] || flag3[x-y+n] ) continue; 
  33.  
  34.         a[x] = y;
  35.  
  36.         flag1[y] = true;
  37.         flag2[x + y] = true;
  38.         flag3[x-y+n] = true;
  39.  
  40.         dfs(x + 1); // 继续下一行 
  41.  
  42.         flag1[y] = false;
  43.         flag2[x + y] = false;
  44.         flag3[x-y+n] = false;
  45.     }
  46. }
  47.  
  48. int main(){
  49.     cin >> n >> k;
  50.     dfs(1);
  51.     return 0;
  52. }

 

题目3：0-1背包问题（经典一题多解题目）

参考代码：

  1. // 0-1背包 
  2. #include <iostream>
  3. using namespace std;
  4. int n , v; 
  5. int v_i[20]; // 第i个物品的体积 
  6. int w_i[20]; // 第i个物品的价值 
  7. int bestw; // 最优价值 ，最优解 
  8. int x[20]; // 物品放入状态数组
  9. int curv; // 当前体积
  10. int curw; //当前价值 
  11.  
  12. int bound(int x){ //计算价值上界
  13.     int rw = 0; //rp:第x个商品~第n个商品全部装入的总价值,先初始化为0
  14.     while(x<=n) 
  15.     {
  16.         rw+=w_i[x];
  17.         x++;
  18.     }
  19.     return rw+curw; //返回当第t个商品不装时,返回前t个商品(不包括第t个)的总价值+剩余的全部商品价值
  20. }
  21. void dfs(int step){
  22.  
  23.     if(step > n){ //某个分支搜索到叶子节点 ，找到一个可行解 
  24.         if(curw > bestw){ //如果当前价值大于最优价值，更新最优解 
  25.             bestw = curw; 
  26.         } 
  27.         return ;
  28.     }
  29.  
  30.     if(curv + v_i[step] <= v){ //判断放入第step个物品不超重，尝试放入 
  31.         x[step] = 1; //标记放入
  32.         curv += v_i[step]; // 累加体积
  33.         curw += w_i[step]; //累加价值 
  34.         dfs(step+1); 
  35.         curv -= v_i[step]; // 回溯，恢复当前体积 
  36.         curw -= w_i[step]; // 回溯，恢复当前价值 
  37.     }
  38.  
  39.     if(bound(step + 1) > bestw){ //判断不放入第step个物品，是否还有必要继续在该分支下搜索 
  40.         x[step] = 0; // 尝试不放入第i个物品
  41.         dfs(step+1); 
  42.     } 
  43. }
  44.  
  45. int main(){
  46.     cin >> n >> v;
  47.     for(int i = 1 ; i <= n; i++){
  48.         cin >> v_i[i] >> w_i[i];
  49.     } 
  50.     dfs(1);
  51.     cout << bestw << endl;
  52.     return 0;
  53. }

 

分支限界算法小结

基本思想

分支限界算法是一种用于解决优化问题和决策问题的算法框架，特别是在解决组合优化问题时非常有效。它类似于回溯算法，但主要用于求解最优化问题，而非枚举所有可能的解。通常，把全部可行解空间反复地分割为越来越小的子集，称为分支；并且对每个子集内的解集计算一个目标下界（对于最小值问题），这称为定界。在每次分枝后，凡是界限超出已知可行解集目标值的那些子集直接剪枝。分支限界法最常使用广度优先算法（Breadth-First Search，BFS）

常见形式

·一般队列式（FIFO）分支限界法：按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。

·优先队列式分支限界法：按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。

问题图谱

题目1：0-1背包问题（基于优先队列的解法）

参考代码：

  1. // 01背包 优先队列式 分支限界 
  2. // 更快找到最优解：先探索最有希望的节点（即优先级最高的节点）
  3. // 更有效的剪枝：优先处理那些最有可能导致最优解的节点。
  4. #include <iostream>
  5. #include <algorithm>
  6. #include <queue>
  7. using namespace std;
  8. int n, V;
  9. int bestp;
  10. struct Item {
  11.     int index, volume, price;
  12.     double density;
  13. }items[110];
  14.  
  15. // 定义队列，用数组模拟 
  16. struct Node{
  17.     int i;  // 代表第i个物品 
  18.     int cv; //  当前总体积
  19.     int cp; // 当前总价值
  20.     int ub;
  21.     bool operator < (const Node& b) const{
  22.         return ub < b.ub;  //up越大越排在前面 ，先出队 
  23.     } 
  24. };
  25.  
  26. bool cmp(const Item &a, const Item &b) {
  27.     return a.density > b.density;
  28. }
  29.  
  30. double bound(int i, int cv, int cp) { 
  31.     double maxp = cp;
  32.     int totv = cv;
  33.     // 使用贪心策略继续添加物品
  34.     while (i <= n && totv + items[i].volume <= V) {
  35.         totv += items[i].volume;
  36.         maxp += items[i].price;
  37.         i++;
  38.     }
  39.     // 如果还有剩余空间，则按比例取最后一个物品的价值
  40.     if (i <= n) {
  41.         maxp += (V - totv) * (items[i].density);
  42.     }
  43.     return maxp;  
  44. }
  45.  
  46. void bfs(){
  47.     //1、初始化队列queue ,将第0个物品放入队列 
  48.     Node cur;
  49.     priority_queue<Node> p_q;
  50.  
  51.     cur.i = 0; //第0个物品 
  52.     cur.cp = 0;
  53.     cur.cv = 0;
  54.     cur.ub  = bound(cur.i+1, cur.cv, cur.cp);//计算上界值 
  55.     p_q.push(cur); //插入优先队列 
  56.  
  57.     //2.循环遍历队列
  58.     while(!p_q.empty()){ //队列不空 
  59.         // 3.取出队头,存入cur
  60.         cur = p_q.top();
  61.         p_q.pop();
  62.  
  63.         int n_i = cur.i+1;
  64.         if(n_i > n) continue;
  65.  
  66.         // 4. 利用产生式规则，拓展cur的关联节点入队
  67.         // 选择下一个物品，并入队 
  68.  
  69.         if(cur.cv + items[n_i].volume <= V){ // 左剪枝 
  70.             Node t;
  71.             t.i = n_i;
  72.             t.cp = cur.cp + items[n_i].price;
  73.             t.cv = cur.cv + items[n_i].volume;
  74.             t.ub  = bound(cur.i+1, cur.cv, cur.cp);//计算上界值 
  75.             bestp = max(bestp,t.cp);
  76.             p_q.push(t); //插入优先队列 
  77.         } 
  78.         // 不选择下一个物品，并入队 
  79.         // 计算上界
  80.         Node t2;
  81.         t2.i = n_i;
  82.         t2.cp = cur.cp;
  83.         t2.cv = cur.cv;
  84.         t2.ub  = bound(cur.i+1, cur.cv, cur.cp);//计算上界值 
  85.  
  86.         if (t2.ub > bestp) {
  87.             p_q.push(t2); //插入优先队列 
  88.         }
  89.     } 
  90. } 
  91.  
  92. int main(){
  93.     // 读入数据 
  94.     cin >> n >> V;
  95.  
  96.     for (int i = 1; i <= n; i++) {
  97.         cin >> items[i].volume >> items[i].price;
  98.         items[i].index = i;
  99.         items[i].density = (double)items[i].price / items[i].volume;
  100.     }
  101.  
  102.     sort(items+1, items+1+n, cmp);
  103.     // 搜索 
  104.     bfs(); 
  105.     // 输出答案 
  106.     cout << bestp << endl;
  107.     return 0;
  108. }

 

题目2：任务分配问题

假设有n个任务和n个人。每个人完成每个任务所需的时间都是不同的。你的任务是分配每个人恰好一个任务，以使完成所有任务的总时间最小。输入第一行包含一个整数n（1≤n≤20），表示任务和人的数量。接下来的n行，每行包含n个整数，表示完成任务的时间矩阵。第i行第j个整数表示第i个人完成第j个任务所需的时间。输出一个整数，表示最小的完成所有任务所需的总时间。

参考代码（含解析）：

  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. using namespace std;
  5.  
  6. int n;
  7. int ans = 2e9;
  8. int a[30][30];
  9.  
  10. struct Node{
  11.     int i; //枚举到第几个人了
  12.     vector<int> ve; //前i个人如何分配任务的编号
  13.     vector<int> used; //第i个任务是否被分配 
  14.     int cost; // 当前总成本
  15.     int lb; //当前节点的下届 
  16.     bool operator < (const Node& b) const {
  17.         return lb > b.lb; //越小的越优先出队 
  18.     }
  19. }; 
  20. // 限界函数 
  21. void bound(Node &e){
  22.     int minsum = 0;
  23.     for(int i = e.i + 1; i <= n; i++){ // 枚举人 
  24.         int min_v = 2e9;
  25.         // 贪心 
  26.         for(int j = 1; j <= n; j++){ // 枚举任务 
  27.             if(e.used[j] == 0 && a[i][j] <= min_v)
  28.                 min_v = a[i][j];
  29.         }
  30.         minsum += min_v;
  31.     } 
  32.     e.lb = e.cost + minsum;
  33. } 
  34.  
  35. void bfs(){
  36.     // 定义一个优先队列 
  37.     priority_queue<Node> p_q;
  38.     Node cur,next;
  39.     cur.i = 0; //根节点
  40.     cur.cost =0;
  41.     cur.used.resize(n+10);
  42.     cur.ve.resize(n+10);
  43.     bound(cur);
  44.     p_q.push(cur); //根节点入队 
  45.  
  46.     while(!p_q.empty()){ // 队列不为空 
  47.         cur = p_q.top();
  48.         p_q.pop();
  49.         for(int j = 1; j <= n; j++){ //枚举任务 
  50.             if(cur.used[j] == 1) continue; //任务被分配过 
  51.             next.i = cur.i + 1;
  52.             next.used = cur.used;
  53.             next.ve = cur.ve;
  54.             next.used[j] = 1;
  55.             next.ve[next.i] = j; //第i个人，被分配了第j个任务 
  56.             next.cost = cur.cost + a[next.i][j];
  57.             bound(next);//计算下届 
  58.             if(next.lb < ans){//剪枝 
  59.                 if(next.i == n){
  60.                     //更新最优解 
  61.                     if(next.cost < ans){
  62.                         ans = next.cost; 
  63.                     }   
  64.                 }else{
  65.                     //入队 
  66.                     p_q.push(next); 
  67.                 }
  68.             }
  69.         }
  70.     }   
  71. }
  72.  
  73. int main(){
  74.     cin >> n;
  75.     for(int i = 1; i <= n; i++){
  76.         for(int j = 1; j <= n; j++)
  77.             cin >> a[i][j];
  78.     }
  79.     bfs();
  80.     cout << ans << endl;
  81.     return 0;
  82. }

 

题目3：二叉树的层序遍历

给出二叉树的根节点root，返回其节点值的层序遍历。（即逐层地，从左到右访问所有节点）。

解析思路：可以使用以下步骤：

·首先根元素入队

·当队列不为空的时候：求当前队列的长度si，依次从队列中取si个元素进行拓展，然后进入下一次迭代。

参考代码：（遍历函数的形式）

  1. vector<vector<int>> levelOrder(TreeNode* root) {
  2.     vector <vector <int>> ret;
  3.     if (!root) {
  4.             return ret;
  5.     }
  6.     queue <TreeNode*> q;
  7.     q.push(root);
  8.     while (!q.empty()) {
  9.         int currentLevelSize = q.size();
  10.         ret.push_back(vector <int> ());
  11.         for (int i = 1; i <= currentLevelSize; ++i) {
  12.             auto node = q.front(); q.pop();
  13.             ret.back().push_back(node->val);
  14.             if (node->left) q.push(node->left);
  15.             if (node->right) q.push(node->right);
  16.         }
  17.     }
  18.     return ret;
  19. }

 

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/盐析白兔/article/detail/147455
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号