!第5章 回溯法.ppt

第5章 回溯法;本章主要知识点;*;*;*;0-1背包问题n=3时的解空间树;*;*;*;子集树（两类典型问题）;当所给问题是确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。排列树通常有(n-1)!个叶结点。因此遍历排列树需要Ω(n!)计算时间。如旅行售货员问题。;回溯法解题步骤;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;public class FlowShop static int n, // 作业数 f1, // 机器1完成处理时间 f, // 完成时间和 bestf; // 当前最优值 static int [][] m; // 各作业所需的处理时间 static int [] x; // 当前作业调度 static int [] bestx; // 当前最优作业调度 static int [] f2; // 机器2完成处理时间;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*; public class Fac5_12{ public static void main(String args[]) { Stamps abc=new Stamps(); int n1=5; int m1=4; int v1[]={0,1,3,11,15,32}; System.out.println(连续邮资问题的最优解 + abc.maxStamp(n1,m1,v1)); for(int k=1;k=n1;k++) System.out.print( +abc.bestx[k]); System.out.println(); } }; class Stamps { static int n; //邮票面值数 static int m; //每张信封允许贴的最多邮票数 static int maxR; //当前最优值 static int maxint; //大整数 static int maxl; //邮资上界 static int [] x; //当前解 static int [] y; //贴出各种邮资所需最少邮票数 static int [] bestx; //当前最优解 ;public static int maxStamp(int nn,int mm,int [] xx) { int maxll=1500; //临时变量，作为邮资上界 n=nn;//有n中不同面值的邮票 m=mm;//一张信封最多允许张贴m张邮票 maxR=0;//最大邮资初始为0 maxint=Integer.MAX_VALUE;//取一个大整数，置初始值 maxl=maxll;//邮资上界 bestx=xx;//当前最优解，由初始面额赋值 x=new int[n+1]; y=new int[maxl+1]; for(int i=0;i=n;i++)x[i]=0;//新的面额初始化，第i个面额为x[i] for(int i=1;i=maxl;i++)y[i]=maxint;//初始化,张贴邮资i最少需要y[i]张邮票 x[1]=1;//最小面额邮票需为1 y[0]=0;//0元面额需0张???票 backtrack(2,1);//递归回溯调用，第2中面值邮票，邮资为1 return maxR; //返回最大邮资 }; private static void backtrack(int i,int r) { for(int j=0;j=x[i-2]*(m-1);j++) //计算最大邮资为多少，m张i种面值的邮票，能够形成邮资范围为0到j（最少包含1张新面额邮票形成的