算法之经典算法思想

古城微笑少年丶 2022-06-04 02:29 241阅读 0赞

# 递归 #

# 分治法 #

# 动态规划 #

参考：  
[https://blog.csdn.net/lz161530245/article/details/76943991][https_blog.csdn.net_lz161530245_article_details_76943991]  
[https://blog.csdn.net/hrn1216/article/details/51534607][https_blog.csdn.net_hrn1216_article_details_51534607] 重点参考文章。  
[https://www.zhihu.com/question/23995189][https_www.zhihu.com_question_23995189] 知乎好的解释

动态规划的本质，是对问题状态的定义和状态转移方程的定义。动态规划是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的方式去解决。如何拆分问题，才是动态规划的核心。而拆分问题，靠的就是状态的定义和状态转移方程的定义。定义好了之后就可以递归定义解决问题，然后通过循环的方式获取最优解。

## **1、求连续子数组的最大和** ##

![这里写图片描述][70]  
1、状态定义：  
**通过状态定义重新描述问题，这个是整个问题的关键，叫做拆分问题**。  
给定一个整形数组，定义F(i)表示以第i个数字结尾的子数组的最大和，求max\[f(i)\]，其中0 =< i < n。  
2、状态转移方程：  
总是可以通过递归的方式定义状态方程。  
![这里写图片描述][70 1]  
当以第i-1个数字结尾的子数组中所有数字的和小于0时，如果把这个负数与第i个数累加，得到的结果比第i个数字本身还要小，所以这种情况下以第i个数字结尾的子数组就是第 i个数字本身。如果以第i-1个数字结尾的子数组中所有数字的和大于0，与第i 个数字累加就得到以第i个数字结尾的子数组中所有数字的和。  
3、按照上述公式直接写代码。可以通过辅助数组打印连续子数组。

#include<stdlib.h>
    #include<iostream>
    #include<vector>
    using namespace std;
    bool gInvalidInput = false;
    int FindGreatestSumOfSubArray(int *pData , int nLength)
    {
        //防御性编程
        if(pData == NULL || nLength == 0){
            gInvalidInput = true;
            return 0;
        }
        int greatestSumStart = 0;
        int Fi = pData[0];
        int MaxFi = 0x80000000;//最小的负数
        //动态规划求解
        for(int i = 1 ; i < nLength ; i++){
            if(Fi <= 0){
                Fi = pData[i];
                greatestSumStart = i;//记录开始索引
            }
            else
                Fi = Fi + pData[i];
            if(Fi > MaxFi)//更新最大Fi
                MaxFi = Fi;
        }
        //打印最大连续子数组
        int tempSum = 0;
        for(int i  = greatestSumStart ; i <nLength ; i++){
            tempSum += pData[i];
            if(tempSum != MaxFi)
                cout << pData[i] << " ";
            else{
                cout << pData[i] << endl;
                break;
            }
        }
        return MaxFi;
    }
    int main(void)
    {
        int a[] = {
       1,-2,3,10,-4,7,2,-5};
        cout << FindGreatestSumOfSubArray(a , sizeof(a)/sizeof(a[0])) << endl;
        return 0;
    }

![这里写图片描述][70 2]

## **2、求最长公共子序列** ##

**1、基本定义：**  
1、子序列： 一个序列A＝a1,a2,……an,中任意删除若干项，剩余的序列叫做A的一个子序列。也可以认为是从序列A按原顺序保留任意若干项得到的序列，子序列与原序列顺序相同，但是不必是连续的。  
例如：  
对序列 1,3,5,4,2,6,8,7来说，序列3,4,8,7 是它的一个子序列。  
对于一个长度为n的序列，它一共有2^n 个子序列，有(2^n – 1)个非空子序列。  
请注意：子序列不是子集，它和原始序列的元素顺序是相关的。  
2、公共子序列： 顾名思义，如果序列C既是序列A的子序列，同时也是序列B的子序列，则称它为序列A和序列B的公共子序列。  
例如：  
对序列 1,3,5,4,2,6,8,7和序列 1,4,8,6,7,5 来说  
序列1,8,7是它们的一个公共子序列。  
请注意： 空序列是任何两个序列的公共子序列。  
例如： 序列1,2,3和序列4,5,6的公共子序列只有空序列。  
3、最长公共子序列  
A和B的公共子序列中长度最长的（包含元素最多的）叫做A和B的公共子序列。  
仍然用序列1,3,5,4,2,6,8,7和序列1,4,8,6,7,5  
它们的最长公共子序列是：  
1,4,8,7  
1,4,6,7  
最长公共子序列的长度是4 。  
请注意: 最长公共子序列不唯一。  
**2、状态定义：**  
依据以下性质，定义状态：  
设A=“a0，a1，…，am”，B=“b0，b1，…，bn”，且Z=“z0，z1，…，zk”为它们的最长公共子序列。不难证明有以下性质：  
（1）如果am=bn，则zk=am=bn，蕴涵意思是“z0，z1，…，z(k-1)”是“a0，a1，…，a(m-1)”和“b0，b1，…，b(n-1)”的一个最长公共子序列且zk是最长公共子序列的一部分；  
（2）如果am!=bn，则若zk!=am，蕴涵意思是“z0，z1，…，zk”是“a0，a1，…，a(m-1)”和“b0，b1，…，bn”的一个最长公共子序列；  
（3）如果am!=bn，则若zk!=bn，蕴涵“z0，z1，…，zk”是“a0，a1，…，am”和“b0，b1，…，b(n-1)”的一个最长公共子序列。  
\*\*于是可以定义用\*\*c\[i,j\]表示Xi和Yj 的LCS的长度（直接保存最长公共子序列的中间结果不现实，需要先借助LCS的长度）。其中Xi = \{x1 … xi\}，Yj=\{y1… yj\}。  
**3、状态转移方程**  
依据上述状态定义可以写出递归的状态方程：  
![这里写图片描述][70 3]  
（1）i=0或者j=0意味着某个子序列长度为0，公共子序列长度自然为0。  
（2）i,j>0，且xi = yj，意味着最长子序列长度等于Xi-1，Yj-1长度加1，并且xi是子序列的一部分，所以当出现这种情况，可以将此标记，以便后序输出子序列。  
（3）i,j>0，且xi != yj，意味着最长子序列长度要么等于Xi-1，Yj，或者等Xi，Yj-1长度，最长即是等于其最大长度。并且xi不是子序列的一部分，所以当出现这种情况，可以将此标记，以便后序输出子序列。有了这个状态转移方程，咱们就可以根据这个思路写出对应的代码了。

![这里写图片描述][70 4]

int LCSLength(char *str1 , char *str2 , int **b)
    {
        int str1Len = strlen(str1);
        int str2Len = strlen(str2);
        int **arrayLength = (int **)malloc((str1Len + 1)*sizeof(int *));//分配指针数组
        for(int i = 0 ; i < str1Len + 1 ; i++)
            arrayLength[i] = (int *)malloc((str2Len + 1)*sizeof(int));//初始化指针数组
        for(int i = 0 ; i < str1Len + 1 ; i++ )//初始化第一列为0，因为j=0
            arrayLength[i][0] = 0;
    
        for(int j = 0 ; j < str2Len + 1 ; j++ )//初始化第一行为0，因为i=0
            arrayLength[0][j] = 0;
    
        //开始递归求解长度,考虑上述三种情况即可
        for(int i = 1 ; i < str1Len + 1 ; i++)
            for(int j = 1 ; j < str2Len + 1 ; j++){
                if(str1[i-1] == str2[j-1]){
                    b[i][j] = 0;//将此节点标志为0，是最长字串一部分，且向左上方搜索
                    arrayLength[i][j] = arrayLength[i-1][j-1]+1;
                }
                else if(arrayLength[i-1][j] >arrayLength[i][j-1]){
                    b[i][j] = 1;//向左边搜索
                    arrayLength[i][j] = arrayLength[i-1][j];
                }
                else if(arrayLength[i-1][j] < arrayLength[i][j-1]){
                    b[i][j] = -1;//向上搜索
                    arrayLength[i][j] = arrayLength[i][j-1];
                }else{
       //相等的话，两边搜索都可以，这里选择向上搜索而已,记住这种思路很重要。
                    b[i][j] = 1;//向上搜索
                    arrayLength[i][j] = arrayLength[i-1][j];
                }
            }
        int StrLen = arrayLength[str1Len][str2Len];//最长公共字串的长度
        for(int i = 0 ; i < str1Len ; i++)
            free(arrayLength[i]);//释放指针数组成员指向的内存
        free(arrayLength);//释放指针数组
        return StrLen;//返回最大公共字串的长度。
    }
    void PrintLCS(int **b , char *str , int i , int j)
    {
        if(i == 0 || j == 0)//到达b的边界了
            return ;
        if(b[i][j] == 0){
            PrintLCS(b,str,i-1,j-1);//从后面开始递归，所以要先递归到子串的前面，然后从前往后开始输出子串。
            cout << str[i-1] << " ";//输出用str[i-1]或str[j-1]都可以。
        }else if(b[i][j] == 1)
            PrintLCS(b,str,i-1,j);//向左方搜索
        else
            PrintLCS(b,str,i,j-1);//向上方搜索
    }
    
    
    int main(void)
    {
    // char *str1 = "ABCBDAB";
    // char *str2 = "BDCABA";
        char *str1 = "13456778";
        char *str2 = "357486782";
        int str1Len = strlen(str1);
        int str2Len = strlen(str2);
        int **b = (int **)malloc((str1Len + 1)*sizeof(int *));//分配指针数组
        for(int i = 0 ; i < str1Len + 1 ; i++){
            b[i] = (int *)malloc((str2Len + 1)*sizeof(int));//初始化指针数组
            memset(b[i] , 0 , (str2Len + 1)*sizeof(int));//全部清0
        }
    
        cout << LCSLength(str1 , str2 , b) << endl;
        PrintLCS(b , str1 , str1Len , str2Len);//5 3-4-6-7-8
    
        return 0;
    }

![这里写图片描述][70 5]  
动态规划问题，难点在于如何将问题划分成子问题。

## **3、硬币面值组合问题** ##

**问题描述**  
　　假设我们有8种不同面值的硬币｛1，2，5，10，20，50，100，200｝数量不限，用这些硬币组合够成一个给定的数值n。例如n=200，那么一种可能的组合方式为 200 = 3 \* 1 + 1＊2 + 1＊5 + 2＊20 + 1 \* 50 + 1 \* 100。问总过有多少种可能的组合方式？类似的题目还有：  
　　\[华为面试题\] 1分2分5分的硬币三种，组合成1角，共有多少种组合？  
　　\[创新工厂笔试题\] 有1分，2分，5分，10分四种硬币，每种硬币数量无限，给定n分钱，有多少中组合可以组成n分钱？  
**问题分析**  
　　给定一个数值sum，假设我们有m种不同类型的硬币\{V1, V2, …, Vm\}，如果要组合成sum，那么我们有  
sum = x1 \* V1 + x2 \* V2 + … + xm \* Vm  
求所有可能的组合数，就是求满足前面等值的系数\{x1, x2, …, xm\}的所有可能个数。  
　　**\[思路1\]** 当然我们可以采用暴力枚举，各个系数可能的取值无非是x1 = \{0, 1, …, sum / V1\}, x2 = \{0, 1, …, sum/ V2\}等等。这对于硬币种类数较小的题目还是可以应付的，比如华为和创新工厂的题目，但是复杂度也很高O（sum/V1 \* sum/V2 \* sum/V3 \* …）  
　　**\[思路2\]** 从上面的分析中我们也可以这么考虑，我们希望用m种硬币构成sum，根据最后一个硬币Vm的系数的取值无非有这么几种情况，xm分别取｛0, 1, 2, …, sum/Vm｝，换句话说，上面分析中的等式和下面的几个等式的联合是等价的。

sum = x1 \* V1 + x2 \* V2 + … + 0 \* Vm  
sum = x1 \* V1 + x2 \* V2 + … + 1 \* Vm  
sum = x1 \* V1 + x2 \* V2 + … + 2 \* Vm  
…  
sum = x1 \* V1 + x2 \* V2 + … + K \* Vm  
　　其中K是该xm能取的最大数值K = sum / Vm。可是这又有什么用呢？不要急，我们先进行如下变量的定义：  
dp\[i\]\[sum\] = 用前i种硬币构成sum 的所有组合数。  
　　那么题目的问题实际上就是求dp\[m\]\[sum\]，即用前m种硬币（所有硬币）构成sum的所有组合数。在上面的联合等式中：当xn=0时，有多少种组合呢？ 实际上就是前i-1种硬币组合sum，有dp\[i-1\]\[sum\]种！ xn = 1 时呢，有多少种组合？ 实际上是用前i-1种硬币组合成(sum - Vm)的组合数，有dp\[i-1\]\[sum -Vm\]种; xn =2呢， dp\[i-1\]\[sum - 2 \* Vm\]种，等等。所有的这些情况加起来就是我们的dp\[i\]\[sum\]。所以：  
dp\[i\]\[sum\] = dp\[i-1\]\[sum - 0\*Vm\] + dp\[i-1\]\[sum - 1\*Vm\] + dp\[i-1\]\[sum - 2\*Vm\] + … + dp\[i-1\]\[sum - K\*Vm\]; 其中K = sum / Vm。这里之所以到达sum / Vm。是因为面值为Vm的个数的无限的，下面将看到这个题目的变体—–面值是有限的。  
![这里写图片描述][70 6]  
换一种更抽象的数学描述就是上式子。  
**通过此公式，我们可以看到问题被一步步缩小**，那么初始情况是什么呢？如果sum=0，那么无论有前多少种来组合0，只有一种可能，就是各个系数都等于0；  
dp\[i\]\[0\] = 1 // i = 0, 1, 2, … , m。如果前0种硬币要组成sum，我们规定为dp\[0\]\[sum\] = 0。  
　　如果我们用二位数组表示dp\[i\]\[sum\], 我们发现第i行的值全部依赖与i-1行的值，所以我们可以逐行求解该数组。

#include <iostream>
    #include <string>
    #include <cmath>
    #include <vector>
    
    using namespace std;
    
    /**************************************************************** * coin Combinations: using dynamic programming * * Basic idea: * dp[i][j] = sum(dp[i-1][j-k*coins[i-1]]) for k = 1,2,..., j/coins[i-1] * dp[0][j] = 1 for j = 0, 1, 2, ..., sum * * Input: * coins[] - array store all values of the coins * coinKinds - how many kinds of coins there are * sum - the number you want to construct using coins * * Output: * the number of combinations using coins construct sum * * Usage: * c[3] = {1, 2, 5}; * int result = coinCombinations(c, 3, 10); * ****************************************************************/
    int coinCombinations(int coins[], int coinKinds, int sum)
    {
        // 2-D array using vector: is equal to: dp[coinKinds+1][sum+1] = {0};
        //初始化为这种是为了存储初始化条件
        vector<vector<int> > dp(coinKinds + 1);
        for (int i = 0; i <= coinKinds; ++i)
        {
            dp[i].resize(sum + 1);
        }
    
        //全部初始化为0
        for (int i = 0; i <= coinKinds; ++i)
        {
            for (int j = 0; j <= sum; ++j)
            {
                dp[i][j] = 0;
            }
        }
    
        //init: dp[i][0] = 1; i = 0, 1, 2 ..., coinKinds
        //Notice: dp[0][0] must be 1, althongh it make no sense that
        //using 0 kinds of coins construct 0 has one way. but it the foundation
        //of iteration. without it everything based on it goes wrong
        for (int i = 0; i <= coinKinds; ++i)
            dp[i][0] = 1;//初始化
        for(int j = 0 ; j <=sum ; j++ )
            dp[0][sum] = 0;//初始化
    
        // iteration: dp[i][j] = sum(dp[i-1][j - k*coins[i-1]])
        // k = 0, 1, 2, ... , j / coins[i-1]
        //开始动态规划
        for (int i = 1; i <= coinKinds; ++i)//从i=1开始计算动态规划
        {
            for (int j = 1; j <= sum; ++j)//每一行开始计算组成sum的种类
            {
                dp[i][j] = 0;
                for (int k = 0; k <= j / coins[i-1]; ++k)//通过递推关系得到
                {
                    dp[i][j] += dp[i-1][j - k * coins[i-1]];//
                }
            }
        }//计算完成所有情况
    
        return dp[coinKinds][sum];//返回组成sum的个数
    }
    
    int main()
    {
        int coins[8] = {
       1, 2, 5, 10, 20, 50, 100, 200};
        int sum = 200;
        int result = coinCombinations(coins, 8, sum);
        cout << "using 8 kinds of coins construct 200, combinations are: " << endl;
        cout << result << endl;
        return 0;
    }

![这里写图片描述][70 7]

## **4、小Q硬币面值组合问题** ##

一堆数字组合成其他数字的问题，都可以通过DP思路解决。  
小Q非常富有，拥有非常多的硬币，小Q的拥有的硬币是有规律的，对于所有的非负整数K,小Q恰好> 各有两个数值为2^k，的硬币，所以小Q拥有的硬币是1，1，2，2，4，4……，小Q卖东西需要支付元钱，请问小Q想知道有多少种组合方案。  
输入：一个n (1<=n<=10^18),代表要付的钱。  
输出：表示小Q可以拼凑的方案数目。  
输入样例：6  
输出样例：3  
即：4+2，4+1+1，2+2+1+1

不同于前面题目：这里面值通过2^k定义，并且每一个面值都是2个。所以前面的dp\[i\]\[sum\]的求法**就需要改一改了，就不是从0到sum / Vm，而是从0到2**，也就是分别只能取出0、1、2枚。  
将上述程序稍作修改，可以解决这道题目。

#include <iostream>
    #include <string>
    #include <cmath>
    #include <vector>
    
    using namespace std;
    
    /**************************************************************** * coin Combinations: using dynamic programming * * Basic idea: * dp[i][j] = sum(dp[i-1][j-k*coins[i-1]]) for k = 1,2,..., j/coins[i-1] * dp[0][j] = 1 for j = 0, 1, 2, ..., sum * * Input: * coins[] - array store all values of the coins * coinKinds - how many kinds of coins there are * sum - the number you want to construct using coins * * Output: * the number of combinations using coins construct sum * * Usage: * c[3] = {1, 2, 5}; * int result = coinCombinations(c, 3, 10); * ****************************************************************/
    int coinCombinations(vector<int> &coins, int coinKinds, int sum)
    {
        // 2-D array using vector: is equal to: dp[coinKinds+1][sum+1] = {0};
        //初始化为这种是为了存储初始化条件
        vector<vector<int> > dp(coinKinds + 1);//内存空间分配好才可以[]
        for (int i = 0; i <= coinKinds; ++i)
        {
            dp[i].resize(sum + 1);
        }
    
        //全部初始化为0
        for (int i = 0; i <= coinKinds; ++i)
        {
            for (int j = 0; j <= sum; ++j)
            {
                dp[i][j] = 0;
            }
        }
    
        //init: dp[i][0] = 1; i = 0, 1, 2 ..., coinKinds
        //Notice: dp[0][0] must be 1, althongh it make no sense that
        //using 0 kinds of coins construct 0 has one way. but it the foundation
        //of iteration. without it everything based on it goes wrong
        for (int i = 0; i <= coinKinds; ++i)
            dp[i][0] = 1;//初始化
        for(int j = 0 ; j <=sum ; j++ )
            dp[0][sum] = 0;//初始化
    
        for(int i = 0 ; i < coins.size() ; i++)
            cout <<coins[i] << endl;
        // iteration: dp[i][j] = sum(dp[i-1][j - k*coins[i-1]])
        // k = 0, 1, 2, ... , j / coins[i-1]
        //开始动态规划
        for (int i = 1; i <= coinKinds; ++i)//从i=1开始计算动态规划
        {
            for (int j = 1; j <= sum; ++j)//每一行开始计算组成sum的种类
            {
                dp[i][j] = 0;//i种硬币组成和j的种类
    
                //通过k <= 2限制了硬币枚数,这里是重点修改的地方//
                for (int k = 0; k <= 2 && k <= j / coins[i-1]; ++k)//通过递推关系得到
                {
                    dp[i][j] += dp[i-1][j - k * coins[i-1]];//dp[i][j] = dp[i-1][j]+dp[i-1][j-conins[j-1]]+dp[i-1][j-2*conins[j-1]]
                }
            }
        }//计算完成所有情况
    
        return dp[coinKinds][sum];//返回组成sum的个数
    }
    
    int main()
    {
        long int sum = 0;
        cin >> sum;
        //int coins[8] = {1, 2, 5, 10, 20, 50, 100, 200};
        //int sum = 200;
    
        //构造银币种类数组
        vector<int> coins;
        for(int i = 0; pow(2,i) < sum ; i++)
            coins.push_back(pow(2,i));
        int result = coinCombinations(coins, coins.size() , sum);
        printf("using %d kinds of coins construct %d, combinations are: %d\n", coins.size() , sum , result);
        return 0;
    }

![这里写图片描述][70 8]

## **5、小Q音乐播放单问题** ##

# 贪心算法 #

# 回溯法（DFS） #

将回溯法对比前面学到的DFS发现，区别仅仅在于DFS内部分支的选择，选择个数与邻接表中元素大小有关。

## 回溯法 ##

有许多问题，当需要从集合中找到解集或者满足什么约束条件的最佳解的时候，可以考虑使用回溯法。回溯法的基本做法就是搜索，通过剪枝（假如约束条件）可以尽量避免不必要的穷举搜索。如果不加以约束条件，那么就是通过递归实现了穷举搜索（通过递归将所有的解集合全部遍历）。  
回溯法的问题答案在解空间树中，按照深度优先的策略（二叉树的前序遍历就是DFS），从根节点出发搜索解空间。**回溯法的解空间分为两种一种是子集树，其二是全排树。而这两种解空间分别对应两类具体的问题**。

## 解空间 ##

**1、子集树**：当我们求解的结果是集合S的某一子集的时候，其对应的解空间是子集树。  
例如对于有n种可选择物品的0-1背包问题，其解空间由长度为n的0-1向量组成，其中某一元素为1，那么这个物体放入背包，否则不放入。该解空间包含了所有可能的0-1赋值。

例如n=3时，其解空间是

*  (0,0,0)：都不放入包中
 *  (0,0,1)：3号物体放入包中
 *  (0,1,0)：2号物体放入包中
 *  (0,1,1)：2、3号物体放入包中
 *  (1,0,0)：1号物体放入包中
 *  (1,0,1)：1、3号放入包中
 *  (1,1,0)：1、2号放入包中
 *  (1,1,1)：1、2、3号放入包中

上述包含了全部可能放入包中的情况，定义了问题的解空间后，还应该将解空间很好地组织起来，使得能用回溯法方便地搜索整个解空间。通常将解空间组织成树或者图的形式。  
例如，对于n=3时的0-1背包问题，可用一颗完全的二叉树表示其解空间，如下图。  
![这里写图片描述][70 9]  
从树根到叶子的任一路径表示解空间中的一个元素。例如，从根节点到节点H的路径相当与解空间中的元素(1,1,1)，**所以对于子集树，其递归分支只有两条**。

void Backtrack(int t) { //t 表示当前是树的第t层，即对集合S中的第t个元素进行判断
        if (t > n)
            output(x);        //大于S中总的元素个数 ，遍历完成 
        else
            for (int i = 0; i <= 1; i++) { //两种可能加入或者不加入到解集合 
                x[t] = i;
                if (Constraint(t) && Bound(t)){     //满足约数条件
                        Backtrack(t + 1);           //对t+1层进行判断 
                    } 
            }
            /*上述循环可简化为两个分支，因为子集树只有两个分支 x[t] = 0; if (Constraint(t) && Bound(t))//满足约数条件，这个就相当于剪枝 Backtrack(t + 1); //对t+1层进行判断 x[t] = 1; if (Constraint(t) && Bound(t))//满足约数条件，满足约数条件，这个就相当于剪枝 Backtrack(t + 1); //对t+1层进行判断 */
    }

2、排列树：求解的结果是集合S的元素的某一种排列的时候，其对应的解空间就是排列树。排列树的分支不仅仅只有2个，例如abcd的全排列在于，选取了一个字母后分支还有3个，选取了第二个字母后分支还有2个，选取了第三个字母后，分支还有1个，因此通用解法里面的循环必须修改为下面的做法。

void Backtrack(int t) { //t表示集合S的第t个元素 
        if (t > n)
            output(x);
        else
            for (int i = t; i <= n; i++){
       //第t个元素与其后面的所有元素进行交换位置
            //每次分支的次数依据剩余的字符个数而定
                swap(x[t], x[i]);
                if (constraint(t) && bound(t)){
       //每个分支对应的约束条件
                        backtrack(t + 1);
                    }
                swap(x[t], x[i]);//还原，为了下次回溯准备
            }
    }

## 常用的剪枝函数 ##

1、约束函数处理不满足约束的子树。  
2、有限界函数剪去得不到最优的子树。

## 实际问题解答 ##

### 1、0-1背包问题（子集树） ###

有4个物体，物体对应的重量为1、2、3、5，其对应的价值为5、8、9、10。背包可放总重量为7的物体。求放入的总价值最大。  
这是典型的子集树的问题。解空间大小为16。穷举法就是可以通过位运算穷举所有的情况，然后对比是否是最优，例如下面的代码就是通过位运算穷举遍历整个解空间。

**穷举法：**  
解空间前面已经说明清楚了，只要重物质量小于等于背包总容量即可，然后比较其总得价值。

#include<iostream>
    #include<math.h>
    using namespace std;
    int Bag=7;    //背包容量
    const int n=4;    //对象数目
    int w[]={
       1,2,3,5}; //对象重量数组
    int v[]={
       5,8,9,10};//对象收益数组
    int main(void)
    {
        int bestv = 0;
        int selection = 0;
        for(int i  = 0 ; i < pow(2,4) ; i++){
       //2^4 = 1 1 1 1,最后一个
            int tempTotalWeight = 0;
            int tempTotalValue = 0;
            for(int j = 0 ; j < n ; j++){
       //通过解计算总重量及总价值
                if( (8 >> j) & i ){
       //先检测最高位是否为1,意味着是否选择第一个物品
                    tempTotalWeight += w[j];
                    tempTotalValue += v[j];
                }
            }
            if(tempTotalWeight <= Bag && tempTotalValue > bestv){
       //总重要小于等于背包可用容量, 且价值大于bestv
                bestv = tempTotalValue;
                selection = i;
            }
        }
        for(int i = 0 ; i < 4 ; i++){
            if((8 >> i) & selection)
                cout << w[i] << " ";
        }
        cout << "the bestv is " << bestv << endl;
        return 0;
    }

![这里写图片描述][70 10]  
遍历整个解空间，将总质量小于等于背包容量的解比较总价值。  
算法复杂度是O(2^n)，非常高。

**回溯穷举法：**  
首先应该明白如果不加剪枝条件的话，01背包问题的回溯方法也是遍历了整个解空间。如下代码，

#define NumOfObject 4//对象数目
    
    int Bag=7;    //背包容量
    
    int weight[]= {
       1 , 2 , 3 , 5}; //对象重量数组
    int value[] = {
       5 , 8 , 9 , 10}; //对象价值数组
    
    int cw;   //当前背包重量
    int cv;   //当前背包价值
    int bestv;//迄今最大的收益
    int selection[NumOfObject];  //对象选择数组，1的时候表示选择该物体，0的表示不选择该组数据
    
    void getBest(int i)
    {
        if(i >= NumOfObject)//递归结束,全部对象判定完毕
        {
            if(cw <= Bag && cv > bestv){
       //比较重量及价值
                bestv = cv;
            }
            for(int i = 0; i < NumOfObject ; i++)//打印出递归遍历解。
                cout << selection[i] << " ";
            cout << endl;
            return;
        }
        selection[i] = 1;
        cw += weight[i];
        cv += value[i];
        getBest(i+1);
        cw -= weight[i];//回溯状态必须恢复
        cv -= value[i];
    
        selection[i] = 0;
        getBest(i+1);//递归另外一个分值，因为没有选取物体，所以cw和cv都不需要改变。
    }
    int main()
    {
        getBest(0);//从第0个物体开始试探
        printf("Finally , bestv is %d.\n",bestv);
        return 0;
    }

![这里写图片描述][70 11]  
从结果中可以看出，这里通过遍历实现了方法1的穷举遍历，唯一的不同就是在遍历的过程中计算了cw和cv，并记录了相应的解。在递归最前面进行判断即可。

**回溯简单剪枝法：**

#include<math.h>
    #define NumOfObject 4//对象数目
    int Bag=7;    //背包容量
    int weight[]= {
       1 , 2 , 3 , 5}; //对象重量数组
    int value[] = {
       5 , 8 , 9 , 10}; //对象价值数组
    
    int cw;   //当前背包重量
    int cv;   //当前背包价值
    int bestv;//迄今最大的收益
    int selection[NumOfObject];  //对象选择数组，1的时候表示选择该物体，0的表示不选择该组数据
    
    void getBest(int i)
    {
        if(i >= NumOfObject)//递归结束,全部对象判定完毕
        {
            if(cw <= Bag && cv > bestv){
       //比较价值
                bestv = cv;
            }
            for(int i = 0; i < NumOfObject ; i++)//打印出递归遍历解。
                cout << selection[i] << " ";
            cout << endl;
            return;
        }
        //每种物品两种选择，所以需要两次递归分支操作，选择了之后，可能需要回溯
        //因此需要将选择还原到之前的状态。
    
        //通过Bag的容量进行简单的剪枝，选择全部小于等于Bag的解
        if(cw + weight[i] <= Bag)//约束条件是背包的容量，进入该节点的左孩子（值为1的孩子）
        {
            selection[i] = 1;//记录选择
            cw += weight[i];
            cv += value[i];
            getBest(i+1);
            cw -= weight[i];//此处回溯，相当于不选择这个节点，需要恢复先前的状态，因为全部解都用到此值
            cv -= value[i];
        }
    
        //不选择，继续遍历右
        selection[i] = 0;//进入该节点的右孩子（值为0的孩子）,不选择此节点
        getBest(i+1);
    }
    
    int main()
    {
        getBest(0);
        printf("Finally , bestv is %d.\n",bestv);
        return 0;
    }

![这里写图片描述][70 12]  
通过简单的剪枝，可以看到，已经将遍历的解缩小到了11中情况。还可以继续优化，可以通过上限函数确定右子树是否需要选择。后面再学习这种情况。  
[对右子树剪枝，继续缩小遍历的解][Link 1]

**拓展：**  
![这里写图片描述][70 13]  
这个题目是背包问题的拓展，仅仅需要在`if(i >= NumOfObject)`里面判断背包容量的情况，因为背包问题选择了全部小于背包容量的解。

2、

# 分支限界法（BFS） #

# 平摊分析 #

[https_blog.csdn.net_lz161530245_article_details_76943991]: https://blog.csdn.net/lz161530245/article/details/76943991
[https_blog.csdn.net_hrn1216_article_details_51534607]: https://blog.csdn.net/hrn1216/article/details/51534607
[https_www.zhihu.com_question_23995189]: https://www.zhihu.com/question/23995189
[70]: /images/20220604/bb9cab5e97e04e8896b2cd8349a40019.png
[70 1]: /images/20220604/e1d2d777584042a99751f913161dd110.png
[70 2]: /images/20220604/fa461cf423584886a401b441b30a9318.png
[70 3]: /images/20220604/77a58dfb27ab4f04b2e7428e5cff73b8.png
[70 4]: /images/20220604/9cb01dbe25c2440caecdc26174e3fab0.png
[70 5]: /images/20220604/89e208d90a1147d0b3a26001569a0eee.png
[70 6]: /images/20220604/3c9a5e7e9fe74d88a74c05b39295493d.png
[70 7]: /images/20220604/07aa029bc151473a91aee43c01ef4a12.png
[70 8]: /images/20220604/62f4807d1f8948bf9fb7b2bfbd73495c.png
[70 9]: /images/20220604/371ca8610b2a43e38cf20183e39aaf2b.png
[70 10]: /images/20220604/8d579ba9791549eda376100a2b8008e4.png
[70 11]: /images/20220604/6e09f95e6ff140afbe13610083532e09.png
[70 12]: /images/20220604/29c9df4b34b04d85b97d015947229129.png
[Link 1]: https://blog.csdn.net/weixin_40184101/article/details/78970586
[70 13]: /images/20220604/725409aa4ed144519578686be8d74105.png