深圳建网站兴田德润优秀,设计网站一般多少钱,wordpress最大文件上传大小修改,桂平市住房和城乡建设局网站一、回溯法 回溯法采用DFS#xff0b;剪枝的方式#xff0c;通过剪枝删掉不满足条件的树#xff0c;提高本身作为穷举搜索的效率。 回溯法一般有子集树和排列树两种方式#xff0c;下面的装载问题和01背包问题属于子集树的范畴。
解空间类型#xff1a; 子集树#xff1…一、回溯法 回溯法采用DFS剪枝的方式通过剪枝删掉不满足条件的树提高本身作为穷举搜索的效率。 回溯法一般有子集树和排列树两种方式下面的装载问题和01背包问题属于子集树的范畴。
解空间类型 子集树所给的问题是从n个元素的集合S中找出满足某种性质的子集例如装载问题、0-1背包问题。 排列树所给的问题是确定n个元素满足某种性质的排列例如旅行商问题。 回溯法所搜索的解结果都在树的叶子结点上一般左树为添加元素1右树为不添加元素0。
剪枝策略 左剪枝当前扩展节点加入左枝后不符合约束条件要求那么就直接剪掉这个子节点及其所有子树不再继续搜索。 右剪枝当前扩展节点加入右枝后已经无法继续寻求最优解后续子树也无法存在最优解或者相比于之前遍历的叶子结点来说更好的最优解那么就剪掉这个子节点及其所有子树不再继续搜索。 二、简单装载问题
1、算法设计 简单装载问题n个集装箱装进一艘载重量为W的轮船其中集装箱的重量为,不考虑集装箱体积。设计一个算法要求选择若干集装箱装进轮船使得不超过载重量W且给出可行解和最优解的箱子装载方式。 算法回溯法子集树算法。 算法参数表 num选择的集装箱数 tw选择的集装箱重量和 rw剩余的集装箱重量和 op表示是否选择该集装箱op1则选择op0则不选 x[ ]最优解的op操作符选择可以用来输出最优的集装箱装载方案 静态变量 n物品个数 w[ ]各种物品的重量 W轮船总重量限额 minnum最优解集装箱存放个数 maxw最优解的总重量 dfs策略
1先判断是否为叶子结点若是则判断该解是否为最优解若是最优解则把op数组存入x数组。最优解条件当前解集装箱存放个数是否小于最优解集装箱存放个数且选择的集装箱和小于轮船限额
2若不是叶子结点则进行扩展操作。
3先进行左扩展若tww[i]W即加入这个物品后总重量不大于轮船限额则继续扩展否则剪枝。
4再进行右扩展若twrw-w[i]W即不加入这个物品时所选集装箱总重和未选集装箱总重的和仍然不小于轮船限额则继续扩展否则剪枝。
2、代码
//回溯法最优装载问题
public class bestload {static int n5;static int minnum9999;static int W10; //w为每个箱子重量static int maxw0; //存放最优解总重量static int w[]{0,5,2,6,4,3};public static void main(String []args){int rw0; //rw为剩余集装箱重量和for(int num:w)rwnum;int op[]new int[w.length]; //存放一个箱子是否装载int x[]new int[w.length];System.out.println(所有可行解);dfs(0,0,rw,op,1,x);System.out.println(最少物品的解);for(int i1;iw.length;i)if(x[i]1)System.out.print(w[i] );}public static void dfs(int num,int tw,int rw,int op[],int i,int x[]){if(in){if(twWnumminnum){maxwtw;minnumnum;for(int j1;jn;j) x[j]op[j];}for(int j1;jn;j) if(op[j]1)System.out.print(w[j] );System.out.println( );}else{op[i]1; //优先左分枝if(tww[i]W) //左分枝条件dfs(num1,tww[i],rw-w[i],op,i1,x);op[i]0;if(twrw-w[i]W)dfs(num,tw,rw-w[i],op,i1,x);}}
}
子集树如下右树部分省略 三、复杂装载问题
1、算法设计 复杂装载问题n个集装箱要装进两艘载重量分别为c1和c2的轮船其中集装箱的重量为,不考虑集装箱体积设计一个算法使得这些集装箱装上这两艘轮船如果不能装载则返回load false。 算法回溯法子集树算法优先第一个轮船装载判断第二个轮船是否能够装载剩余集装箱。 dfs策略
1先判断是否为叶子结点若是则判断该解是否为最优解若是最优解则把op数组存入x数组。最优解条件当前选择的集装箱和是否大于第一个轮船的最优集装箱装载重量且选择的集装箱和小于第一个轮船限额
2若不是叶子结点则进行扩展操作。
3先进行左扩展若tww[i]c1即加入这个物品后总重量不大于第一个轮船限额则继续扩展否则剪枝。
4再进行右扩展若twrw-w[i]maxw即不加入这个物品时所选集装箱总重和未选集装箱总重的和仍然不小于第一个轮船的最优装载重量和则继续扩展否则剪枝。
2、代码
//回溯法复杂装载问题
public class complexbestload {static int n3;static int minnum9999;static int c150; //w为每个箱子重量static int c250;static int maxw0; //存放最优解总重量static int w[]{0,10,40,40};public static void main(String []args){int rw0; //rw为剩余集装箱重量和for(int num:w)rwnum;int op[]new int[w.length]; //存放一个箱子是否装载int x[]new int[w.length];dfs(0,0,rw,op,1,x);judge(x);}public static void dfs(int num,int tw,int rw,int op[],int i,int x[]){if(in) //dfs搜索到最后一层所有的货物都试了一遍则输出最优解{if(twc1twmaxw){maxwtw;for(int j1;jn;j)x[j]op[j];}}else{op[i]1; //优先左分枝if(tww[i]c1) //左分枝条件dfs(num1,tww[i],rw-w[i],op,i1,x);op[i]0;if(twrw-w[i]maxw)dfs(num,tw,rw-w[i],op,i1,x);}}public static void judge(int x[]){int total0;for(int i1;iw.length;i)if(x[i]0)totalw[i];if(totalc2){System.out.print(c1:);for(int i1;iw.length;i)if(x[i]1)System.out.print(w[i] );System.out.println();System.out.print(c2:);for(int i1;iw.length;i)if(x[i]0)System.out.print(w[i] );} else System.out.println(load false);}
}四、0-1背包问题
1、算法设计 0-1背包问题给定n个物品和一个背包物品重量为价值为背包容量为c请设计一种算法放入若干物品后背包中物品总价值最大。 算法回溯法子集树算法。左剪枝结合贪心算法。 初始化首先对w数组和v数组进行重新排序按照a数组即单位重量价值最高的优先。下面代码使用快速排序。 dfs策略
1先判断是否为叶子结点若是则判断该解是否为最优解若是最优解则把op数组存入x数组最优解maxv替换为当前所选物品的总重量。最优解条件当前所选物品总重量不大于背包限额且所选物品的价值大于当前最优解maxv。
2若不是叶子结点则进行扩展操作。
3先进行左扩展计算左分枝后使用贪心算法计算已选物品与若干剩余物品在背包未超重情况下的最大价值。若greedmaxv该最大价值已经大于当前已知最优解maxv且tww[i]W当前已选物品的总重量加上新物品仍然不大于背包限额则进行扩展否则剪枝。
4再进行右扩展若twrw-w[i]maxw即不加入这个物品时所选物品总重和剩余物品总重的和仍然不小于背包限额则继续扩展否则剪枝。
2、代码
//回溯法解决0-1背包问题
public class backage {static int W10;static int maxv0; //存放最优解价值public static void main(String[] args){double w[]{0,2,1,3,4,6};double v[]{0,3,2,4,5,8};int nw.length-1;double rw0;double a[]new double[w.length];int op[]new int[w.length]; //存放当前叶子结点的解int x[]new int[w.length]; //存放最优解for(int i1;iw.length;i)a[i]v[i]/w[i];for(int i1;iw.length;i)rww[i];//快排quickSort(a, w, v, 1, n);//回溯dfs(w,v,0,0,rw,op,x,1);int total0;for(int j1;jw.length;j){if(x[j]1){ System.out.print(w[j] );totalv[j];}}System.out.println();System.out.println(Max value:total);}//快速排序public static void quickSort(double arr[],double w[],double v[],int low,int high){int ilow;int jhigh;int t;if(lowhigh)return;double tmparr[low];while(ij){while(ijtmparr[j]){j--;}; //注意由于降序排列所以为tmparr[j]while(ijtmparr[i]){i;}; //同理tmparr[i]if(ij){swap(arr,i,j);swap(w, i, j);swap(v,i,j);}}swap(arr,low,i);swap(w,low,i);swap(v,low,i);quickSort(arr, w,v,low, j-1);quickSort(arr,w,v,j1,high);}//交换同一数组的两个值public static void swap(double arr[],int i,int j){double t;tarr[i];arr[i]arr[j];arr[j]t;}//回溯法public static void dfs(double w[],double v[],int num,double tw, double rw, int op[],int x[],int i){if(iw.length-1){if(twW){int tot0;for(int j1;jw.length;j){if(op[j]1){totv[j];}}if(totmaxv){for(int j1;jw.length;j)x[j]op[j];maxvtot;}}}else{op[i]1; //优先左分枝double greedgreedy(op, v, w, i);if(tww[i]Wgreedmaxv) //左分枝条件dfs(w,v,num1,tww[i],rw-w[i],op,x,i1);op[i]0;if(twrw-w[i]W)dfs(w,v,num,tw,rw-w[i],op,x,i1);}}//左剪枝贪心计算public static double greedy(int op[],double v[],double w[],int i){double totv0;double totw0;for(int j1;ji;j){if(op[j]1){ totvv[j];totww[j];}}for(int ji1;jw.length;j){if(totww[j]W){totww[j];totvv[j];}else{totv(W-totw)*v[j]/w[j];totwW;break;}}return totv;}
}
