算法设计基础——综合

算法设计基础中最基础的几种算法：分治法、减治法、贪心法、动态规划法、回溯法基本都掌握后，我们现在可以对这些算法做整体的比较，本次实验使用蛮力法、动态规划法、回溯法来求解0/1背包问题，来比较各个算法的优劣。

1. 蛮力法

问题描述：

有n个物品待装入背包，给出各个物品的价值和重量以及背包的容量，需要求出一个最佳的方案使得装入背包的物品总价值最高。此问题为子集问题，总共的方案数有2^n种，这些方案可以用一串二进制序列表示：000、001、010等，这样要求出一个个的方案只需要求出一系列的二进制数即可，然后再对这些方案一个个试探判断是否符号条件，最后找出最佳方案。

解决办法：

此题为子集问题，考虑子集的形式，使用01表示是否集合中的某个元素，这样子集的序列为{0，0，0}、{0，0，1}等，这些序列可以看做二进制的数，二进制数0到2^n-1，这些二进制序列即是集合的子集，这样只要求出二进制0到2^n-1即可求得所有子集序列。由于转换的二进制需要按位存放在数组中，可以直接把十进制数看做二进制数，循环对2取mod再除以2，得到每一位的数字，这些即构成了一串序列。通过对这些序列一一试探得到可能解，再从这些可能解中得到最优解。

算法描述：

算法：0/1背包问题蛮力法knapsackByBF

输入：n个物品的价值和重量、背包的容量

输出：最佳方案

过程：

1. 定义变量bestValue存储最大价值并初始化为最小值
2. 定义二维数组x[2^n][n]存储所有方案
3. 定义i循环变量i并初始化为零，i从0到2^n-1，重复执行如下操作：
   1. 定义变量temp并赋值为i
   2. 定义循环变量j并初始化为0，j从0到n-1，重复执行如下操作：
      1. X[i][j]取temp个位的值（二进制）
      2. 判断该物品是否能装入背包，计算当前已经装入背包的物品的重量与价值，不能装入则置x[i][j]为0
      3. 更新最大值
      4. j++;
   3. i++;
4. 返回最佳方案

对于一个简单的测试数据：

        int[] weight1 = {7, 3, 4, 5};
        int[] value1 = {42, 12, 40, 35};
        int capacity = 15;

计算流程如下图：

计算每一种可能解的结果，在所有解中寻找最优解。

时间复杂度计算：所要找出的方案数为2^n种，依次试探每一种方案，每一种方案的处理时间复杂度为O（1），总时间复杂度为O（2^n）。

算法实现：

public static int knapsackByBF(int[] weight, int[] value, int n, int

?capacity){
??? int i, j;
??? int temp;?????? //临时存储各位的值
??? int tempWeight;
??? int bestValue = Integer.MIN_VALUE;????? //最大价值
??? int index = -1;????? //最大价值的方案下标
??? //首先使用蛮力法求出集合的所有子集
??? for(i = 0; i < Math.pow(2, n); i++){??? //一共2^n个子集
??????? tempWeight = 0;
??????? temp = i;
??????? for (j = 0; j < n; j ++){
??????????? //temp = i % 2;?????????? //取末位的值
??????????? x[i][j] = temp % 2;???? //将该数的所有位按二进制存放进数组，这个二进制序列即位集合的一个子集
??????????? if(tempWeight + x[i][j] * weight[j] <= capacity) {???? //若剩余容量足够则装入背包
??????????????? tempWeight += x[i][j] * weight[j];
??????????????? tValue[i] += x[i][j] * value[j];
??????????? }
??????????? else{
??????????????? x[i][j] = 0;??????? //无法装入则为0
??????????????? break;????????????? //此物品无法装入，后面的物品也不能装入，直接退出循环
??????????? }

??????????? temp /= 2;????? //继续存入下一位数字

??????? }
??????? if(tValue[i] > bestValue) {?????? //更新最大值
??????????? bestValue = tValue[i];
??????????? index = i;
??????? }
??? }
??? return index;
}

测试数据：

测试结果：

2. 动态规划法

问题描述：

有n个物品待装入背包，给出各个物品的价值和重量以及背包的容量，需要求出一个最佳的方案使得装入背包的物品总价值最高，使用动态规划法实现。考虑规划过程，i个物品j容量的背包的最大价值为不装入第i个物品和装入第i个物品两种选择中价值最大的一种。可采用填表法，依次将各种情况填写出来，直到i=n，j=capacity（n为物品数，capacity为背包容量）。

解决办法：

采用填表法实现，需要得到的是一个n个物品，capacity背包容量的最佳方案，把原问题分解多个i个物品，j背包容量的子问题，i从0到n，j从0到capacity，对每一个子问题进行求解，由子问题的解推出原问题的解。每个子问题的求解过程如下：背包容量足够时当前子问题的解为装入这个物品和不装入这个物品两种方案中价值较大者，背包容量不足时子问题的解为不装入这个物品。

对于数据：

        int[] weight1 = {7, 3, 4, 5};
        int[] value1 = {42, 12, 40, 35};
        int capacity = 15;

计算流程如下图：

对每一行没一列进行填表，后面的结果根据前面得到的结果推出，依次计算到i=n，j=capacity为止。

算法描述：

算法：0/1背包问题蛮力法knapsackByBF

输入：n个物品的价值value[]和重量weight[]、背包的容量capacity

输出：最佳方案

过程：

1. 定义二维数组v[n][capacity]存储所有子问题
2. 填写第一行，v[0][j]=0，j取0到capacity
3. 填写第一列，v[i][0]=0，i取0到n
4. 填写每一行：
   1. 若j<weight[i]，该物品重量大于背包容量，无法放入，v[i][j]=v[i-1][j]，
   2. 若j>=weight[i]，该物品可以放入，v[i][j]取v[i-1][j]和v[i-1][j-weight[i]+value[i]二者的较大者
5. 返回v[n][capacity]；

算法实现：

public static int knapsackByDP(int[] weight, int[] value, int n, int
 capacity){
??? int i, j;
??? int[][] v = new int[100][100];
??? for(j = 0; j <= capacity; j++)???????? //填写第一行
??????? v[0][j] = 0;
??? for(i = 0; i <= n; i++)???????????????? //填写第一列
??????? v[i][0] = 0;
??? for(i = 1; i <= n; i++)???????????????? //填写其他行(i为物品)
??????? for(j = 1; j <= capacity; j++){????? //j为背包剩余容量
??????????? if(j < weight[i])?????????????? //背包容量不足，不放人这个物品
??????????????? v[i][j] = v[i - 1][j];
??????????? else
??????????????? v[i][j] = Math.max(v[i-1][j], v[i-1][j-weight[i]] + value[i]);
??????? }
??? i = n;
??? j = capacity;
??? for(; i > 0; i--) {?????? //回溯寻找求解方案
??????? if (v[i][j] > v[i - 1][j]) {??? //v[i][j]大于v[i-1][j]则说明该物品被装入
??????????? xl[i] = 1;
??????????? j -= weight[i];
??????? }
??????? else
??????????? xl[i] = 0;
??? }
??? return v[n][capacity];
}

测试数据：

?

测试结果：

3. 回溯法

问题描述：

有n个物品待装入背包，给出各个物品的价值和重量以及背包的容量，需要求出一个最佳的方案使得装入背包的物品总价值最高，使用回溯法实现。每一个物品都有装入和不装入两种选择，依次对这两种选择进行试探，直到试探到最后一个元素或者超出背包容量。

解决办法：

每一个物品都有装入和不装入两种选择，依次对这两种选择进行试探，直到试探到最后一个元素或者超出背包容量。

算法描述：

算法：0/1背包问题回溯法knapsackByBacktrack

输入：n个物品的价值value[]和重量weight[]、背包的容量capacity

输出：最佳方案

过程：

1. 如果所有物品均探测完毕或装入背包的物品重量超出背包容量：
   1. 如果重量超过范围，算法结束；
   2. 否则当前已探索出一个方案，进行更新最大值操作；
2. 探索不装入该物品的方案
3. 探索装入该物品的方案

时间复杂度计算：总共有2^n种方案，回溯法需要依次对所有方案进行试探，每种方案试探的时间复杂度为O（1），则总时间复杂度为O（2^n）。

算法实现：

public static void knapsackByBacktrack(int count, int weightSum, int 
capacity, int valueSum){
??? if(count == n || weightSum >= capacity){ //所有物品都走完或超出背包重量则路线寻找完毕
??????? if(weightSum > capacity)
??????????? return;
??????? if(valueSum > bestValueb)
??????????? bestValueb = valueSum;
??????? //visited[pathCount] = valueSum;???? //存储该方案的总价值以便后续判断
??????? pathCount++;
??????? System.arraycopy(path[pathCount - 1], 0, path[pathCount], 0, count);
??????? return;
??? }
??? path[pathCount][count] = 0;
??? knapsackByBacktrack(count + 1, weightSum, capacity, valueSum);
??? path[pathCount][count] = 1;
??? knapsackByBacktrack(count + 1, weightSum+weight[count],
??????????? capacity, valueSum + value[count]);

}

测试数据：

测试结果：

4. 总结

蛮力法是最粗暴简单的一种算法，它的基本思想就是寻找所有的可能解，将所有可能的解都计算出来，根据题目的要求寻找满足条件的解，或者找出最优解。蛮力法一般的实现方法是循环遍历，根据题目的要求，遍历各种情况，对每种情况进行计算，最后得出可行解或者找出最优解。蛮力法因为其简单粗暴的特点，比较适合初学者入门，使用蛮力法非常容易实现，而且也很容易计算蛮力法的时间复杂度，此外，使用蛮力法基本不需要什么限制，因此基本对所有问题都能求解。但是也正是因为蛮力法简单粗暴的特点，它可以说是完全没有对问题简化，计算复杂度非常的高，基本就是所有算法中计算复杂度最高的一种算法，也因此其他算法经常会与蛮力法进行比较。

动态规划法与分治法有些类似，动态规划法是将问题划分为重叠的多个子问题，然后根据题目给出一个动态规划函数，这是动态规划法的关键，动态规划函数是子问题满足的递推关系式，在计算每个子问题的时候，都是使用动态规划函数从前面计算得到的子问题的解推导出本身的解。因此动态规划法再计算时会将前面计算的结果保存，后面的子问题在计算时可以直接使用前面的计算结果，不用重复计算，因此动态规划法避免了大量的计算。动态规划法是根据子问题的最优解求出的原问题的最优解，这个最优解是全局最优的，因为它是根据所有子问题一个个推导出来的。对于能够给出动态规划函数的问题，动态规划法都能够求解出最优解，对于多阶段最优化问题，动态规划法是非常适合的。

回溯法是基于深度优先搜索原理的一种搜索可能解的方法，它的搜索过程是深度优先搜索，也就是它会优先从一个结点的一条分支一直走下去，知道该分支路走不通了或者不满足约束条件才会停下，再回溯到上一个结点，从上一个结点的另一条分支继续向下一直探索。回溯法看上去和蛮力法很像，都是暴力探索可能的解，但回溯法与蛮力法最大的不同在于，回溯法不会探索完所有的解，它会根据一个约束条件判断当前结点的一条分支是否可行，如果不可行，回溯法会立即回溯，寻找另一个可能的解。不过回溯法的计算复杂度仍然是比较高的，通常比蛮力法也差不了多少，只有在某些问题上比较适合，比如迷宫寻找一条可能的通路，但在求解最优解的问题上，回溯法的性能就非常差了，因为它要计算每一个可能解，从所有可能解中找出最优解。