家具网站模板,商品网站建设,东莞公司展厅设计公司,站长之家官网查询算法设计基础中最基础的几种算法#xff1a;分治法、减治法、贪心法、动态规划法、回溯法基本都掌握后#xff0c;我们现在可以对这些算法做整体的比较#xff0c;本次实验使用蛮力法、动态规划法、回溯法来求解0/1背包问题#xff0c;来比较各个算法的优劣。
1. 蛮力法
…算法设计基础中最基础的几种算法分治法、减治法、贪心法、动态规划法、回溯法基本都掌握后我们现在可以对这些算法做整体的比较本次实验使用蛮力法、动态规划法、回溯法来求解0/1背包问题来比较各个算法的优劣。
1. 蛮力法
问题描述
有n个物品待装入背包给出各个物品的价值和重量以及背包的容量需要求出一个最佳的方案使得装入背包的物品总价值最高。此问题为子集问题总共的方案数有2^n种这些方案可以用一串二进制序列表示000、001、010等这样要求出一个个的方案只需要求出一系列的二进制数即可然后再对这些方案一个个试探判断是否符号条件最后找出最佳方案。
解决办法
此题为子集问题考虑子集的形式使用01表示是否集合中的某个元素这样子集的序列为{000}、{001}等这些序列可以看做二进制的数二进制数0到2^n-1这些二进制序列即是集合的子集这样只要求出二进制0到2^n-1即可求得所有子集序列。由于转换的二进制需要按位存放在数组中可以直接把十进制数看做二进制数循环对2取mod再除以2得到每一位的数字这些即构成了一串序列。通过对这些序列一一试探得到可能解再从这些可能解中得到最优解。
算法描述 算法0/1背包问题蛮力法knapsackByBF 输入n个物品的价值和重量、背包的容量 输出最佳方案 过程 定义变量bestValue存储最大价值并初始化为最小值定义二维数组x[2^n][n]存储所有方案定义i循环变量i并初始化为零i从0到2^n-1重复执行如下操作 定义变量temp并赋值为i定义循环变量j并初始化为0j从0到n-1重复执行如下操作 X[i][j]取temp个位的值二进制判断该物品是否能装入背包计算当前已经装入背包的物品的重量与价值不能装入则置x[i][j]为0更新最大值j;i;返回最佳方案 对于一个简单的测试数据 int[] weight1 {7, 3, 4, 5};int[] value1 {42, 12, 40, 35};int capacity 15;
计算流程如下图 计算每一种可能解的结果在所有解中寻找最优解。
时间复杂度计算所要找出的方案数为2^n种依次试探每一种方案每一种方案的处理时间复杂度为O1总时间复杂度为O2^n。
算法实现
public static int knapsackByBF(int[] weight, int[] value, int n, intcapacity){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; //无法装入则为0break; //此物品无法装入后面的物品也不能装入直接退出循环}temp / 2; //继续存入下一位数字}if(tValue[i] bestValue) { //更新最大值bestValue tValue[i];index i;}}return index;
}
测试数据 测试结果 2. 动态规划法
问题描述
有n个物品待装入背包给出各个物品的价值和重量以及背包的容量需要求出一个最佳的方案使得装入背包的物品总价值最高使用动态规划法实现。考虑规划过程i个物品j容量的背包的最大价值为不装入第i个物品和装入第i个物品两种选择中价值最大的一种。可采用填表法依次将各种情况填写出来直到injcapacityn为物品数capacity为背包容量。
解决办法
采用填表法实现需要得到的是一个n个物品capacity背包容量的最佳方案把原问题分解多个i个物品j背包容量的子问题i从0到nj从0到capacity对每一个子问题进行求解由子问题的解推出原问题的解。每个子问题的求解过程如下背包容量足够时当前子问题的解为装入这个物品和不装入这个物品两种方案中价值较大者背包容量不足时子问题的解为不装入这个物品。
对于数据 int[] weight1 {7, 3, 4, 5};int[] value1 {42, 12, 40, 35};int capacity 15;
计算流程如下图 对每一行没一列进行填表后面的结果根据前面得到的结果推出依次计算到injcapacity为止。
算法描述 算法0/1背包问题蛮力法knapsackByBF 输入n个物品的价值value[]和重量weight[]、背包的容量capacity 输出最佳方案 过程 定义二维数组v[n][capacity]存储所有子问题填写第一行v[0][j]0j取0到capacity填写第一列v[i][0]0i取0到n填写每一行 若jweight[i]该物品重量大于背包容量无法放入v[i][j]v[i-1][j]若jweight[i]该物品可以放入v[i][j]取v[i-1][j]和v[i-1][j-weight[i]value[i]二者的较大者返回v[n][capacity] 算法实现
public static int knapsackByDP(int[] weight, int[] value, int n, intcapacity){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];elsev[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];}elsexl[i] 0;}return v[n][capacity];
}
测试数据 测试结果 3. 回溯法
问题描述
有n个物品待装入背包给出各个物品的价值和重量以及背包的容量需要求出一个最佳的方案使得装入背包的物品总价值最高使用回溯法实现。每一个物品都有装入和不装入两种选择依次对这两种选择进行试探直到试探到最后一个元素或者超出背包容量。
解决办法
每一个物品都有装入和不装入两种选择依次对这两种选择进行试探直到试探到最后一个元素或者超出背包容量。
算法描述 算法0/1背包问题回溯法knapsackByBacktrack 输入n个物品的价值value[]和重量weight[]、背包的容量capacity 输出最佳方案 过程 如果所有物品均探测完毕或装入背包的物品重量超出背包容量 如果重量超过范围算法结束否则当前已探索出一个方案进行更新最大值操作探索不装入该物品的方案探索装入该物品的方案 时间复杂度计算总共有2^n种方案回溯法需要依次对所有方案进行试探每种方案试探的时间复杂度为O1则总时间复杂度为O2^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, weightSumweight[count],capacity, valueSum value[count]);}
测试数据 测试结果 4. 总结
蛮力法是最粗暴简单的一种算法它的基本思想就是寻找所有的可能解将所有可能的解都计算出来根据题目的要求寻找满足条件的解或者找出最优解。蛮力法一般的实现方法是循环遍历根据题目的要求遍历各种情况对每种情况进行计算最后得出可行解或者找出最优解。蛮力法因为其简单粗暴的特点比较适合初学者入门使用蛮力法非常容易实现而且也很容易计算蛮力法的时间复杂度此外使用蛮力法基本不需要什么限制因此基本对所有问题都能求解。但是也正是因为蛮力法简单粗暴的特点它可以说是完全没有对问题简化计算复杂度非常的高基本就是所有算法中计算复杂度最高的一种算法也因此其他算法经常会与蛮力法进行比较。
动态规划法与分治法有些类似动态规划法是将问题划分为重叠的多个子问题然后根据题目给出一个动态规划函数这是动态规划法的关键动态规划函数是子问题满足的递推关系式在计算每个子问题的时候都是使用动态规划函数从前面计算得到的子问题的解推导出本身的解。因此动态规划法再计算时会将前面计算的结果保存后面的子问题在计算时可以直接使用前面的计算结果不用重复计算因此动态规划法避免了大量的计算。动态规划法是根据子问题的最优解求出的原问题的最优解这个最优解是全局最优的因为它是根据所有子问题一个个推导出来的。对于能够给出动态规划函数的问题动态规划法都能够求解出最优解对于多阶段最优化问题动态规划法是非常适合的。
回溯法是基于深度优先搜索原理的一种搜索可能解的方法它的搜索过程是深度优先搜索也就是它会优先从一个结点的一条分支一直走下去知道该分支路走不通了或者不满足约束条件才会停下再回溯到上一个结点从上一个结点的另一条分支继续向下一直探索。回溯法看上去和蛮力法很像都是暴力探索可能的解但回溯法与蛮力法最大的不同在于回溯法不会探索完所有的解它会根据一个约束条件判断当前结点的一条分支是否可行如果不可行回溯法会立即回溯寻找另一个可能的解。不过回溯法的计算复杂度仍然是比较高的通常比蛮力法也差不了多少只有在某些问题上比较适合比如迷宫寻找一条可能的通路但在求解最优解的问题上回溯法的性能就非常差了因为它要计算每一个可能解从所有可能解中找出最优解。
