从零开始 2020-04-30
public class Greed { /*贪心算法:在对问题求解时, 没一部的选择都是最优的选择*/ public static void main(String[] args) { System.out.println("121212"); //创建广播电台 Map<String, HashSet<String>> broadcasts = new HashMap<String, HashSet<String>>(); HashSet<String> hashSet1 = new HashSet<>(); hashSet1.add("北京"); hashSet1.add("上海"); hashSet1.add("天津"); HashSet<String> hashSet2 = new HashSet<>(); hashSet2.add("广州"); hashSet2.add("北京"); hashSet2.add("深圳"); HashSet<String> hashSet3 = new HashSet<>(); hashSet3.add("成都"); hashSet3.add("上海"); hashSet3.add("杭州"); HashSet<String> hashSet4 = new HashSet<>(); hashSet4.add("上海"); hashSet4.add("天津"); HashSet<String> hashSet5 = new HashSet<>(); hashSet5.add("杭州"); hashSet5.add("大连"); broadcasts.put("K1",hashSet1); broadcasts.put("K2",hashSet2); broadcasts.put("K3",hashSet3); broadcasts.put("K4",hashSet4); broadcasts.put("K5",hashSet5); /*allAreas存放所有的地区*/ HashSet<String> allAreas = new HashSet<>(); allAreas.add("北京"); allAreas.add("上海"); allAreas.add("天津"); allAreas.add("广州"); allAreas.add("深圳"); allAreas.add("成都"); allAreas.add("杭州"); allAreas.add("大连"); //存放选择的电台集合 ArrayList<String> selects = new ArrayList<>(); HashSet<String> tempSet = new HashSet<>();//交集 //最大覆盖电台数 String maxKey = null; while (allAreas.size()!=0){ maxKey=null;//置空 for (String key : broadcasts.keySet()){ tempSet.clear(); //取出key 对应的地区 HashSet<String> areas = broadcasts.get(key); tempSet.addAll(areas); //取交集 tempSet.retainAll(allAreas); if (tempSet.size()>0 && (maxKey ==null||tempSet.size()>broadcasts.get(maxKey).size())){ maxKey =key; } } if (maxKey!=null){ selects.add(maxKey); //将广播电台成all清除; allAreas.removeAll(broadcasts.get(maxKey)); } } System.out.println("得到的选择结果 "+selects); } } 马踏棋盘 在8×8方格的棋盘上,从任意指定方格出发,为马寻找一条走遍棋盘每一格并且只经过一次的一条路径。 【初步设计】 首先这是一个搜索问题,运用深度优先搜索进行求解。算法如下: ⒈ 输入初始位置坐标x,y; ⒉ 步骤 c: 如果c> 64输出一个解,返回上一步骤c-- (x,y) ← c 计算(x,y)的八个方位的子结点,选出那些可行的子结点 循环遍历所有可行子结点 public class ma { //马在一个点时,能走的方向有8个; static final int[] fx = {-1,-2,-2,-1,1,2,2,1}; static final int[] fy={2,1,-1,-2,-2,-1,1,2}; static final int N =8; //棋盘的大小; static int[][] board = new int[N][N];//马走的棋盘; class manode{ int x; //x坐标 int y; //y坐标 int way; //该点有多少种走法; } //定义一个内部类,马所在点的信息; int wayout(int x,int y){ int tx,ty; int count = 0; if(x<0||y<0||x>=N||y>=N||board[x][y]>0){ return -1; } //当点超出边界或者所在的点的值不为0时,返回-1; for(int i = 0;i<N;i++){ tx = x+fx[i]; ty = y+fy[i]; if(tx<0||ty<0||tx>=N||ty>=N){ continue;//如果点的另一个点超出边界时,就continue; } if(board[tx][ty] == 0){ count++;//否则计数器计数; } } return count; }//计算该点的走法有多少种; void sort(manode[] hn,int n){ int i,j,k; manode temp; //临时对象,用来排序交换; for(i=0;i<n;i++){ for(k=i,j=i+1;j<n;j++){ if(hn[j].way<hn[k].way) k=j; } if(k>i){ temp = hn[i]; hn[i] = hn[k]; hn[k] = temp; } } }//将走法的数量进行排序,将最少的走法放在数组的头; void dfs(int x,int y,int count){ int i,tx,ty; manode[] t = new manode[N]; if(count >N*N){ output(); return; } //当count计数器超过64时,打印输出; for(i=0;i<N;i++){ tx = x+fx[i]; ty = y+fy[i]; manode h = new manode(); t[i]=h; t[i].x = tx; t[i].y = ty; t[i].way = wayout(tx,ty); } sort(t,N); for(i = 0;t[i].way<0;i++) ; for(;i<N;i++){ tx = t[i].x; ty = t[i].y; board[tx][ty] = count; dfs(tx,ty,count+1); board[tx][ty] = 0;//遇到死路时,回退回去,并将其变成0; } }//深度搜索与回溯算法; public static void main(String[] args) { int x,y; Scanner input = new Scanner(System.in); System.out.println("please input x,y:"); x = input.nextInt(); y = input.nextInt(); ma test = new ma(); board[x][y]=1; test.dfs(x, y, 2); } void output(){ for(int i = N-1;i>=0;i--){ for(int j = 0;j<N;j++){ System.out.printf("%d\t",board[i][j]); } System.out.printf("\n\n\n"); } System.exit(0); } //打印输出函数; }
publicclass ma {//马在一个点时,能走的方向有8个;staticfinalint[] fx = {-1,-2,-2,-1,1,2,2,1}; staticfinalint[] fy={2,1,-1,-2,-2,-1,1,2}; staticfinalint N =8; //棋盘的大小;staticint[][] board = newint[N][N];//马走的棋盘;class manode{int x; //x坐标int y; //y坐标int way; //该点有多少种走法; } //定义一个内部类,马所在点的信息;int wayout(int x,int y){ int tx,ty; intcount = 0; if(x<0||y<0||x>=N||y>=N||board[x][y]>0){ return -1; } //当点超出边界或者所在的点的值不为0时,返回-1;for(int i = 0;i<N;i++){ tx = x+fx[i]; ty = y+fy[i]; if(tx<0||ty<0||tx>=N||ty>=N){ continue;//如果点的另一个点超出边界时,就continue; } if(board[tx][ty] == 0){ count++;//否则计数器计数; } } returncount; }//计算该点的走法有多少种;void sort(manode[] hn,int n){ int i,j,k; manode temp; //临时对象,用来排序交换;for(i=0;i<n;i++){ for(k=i,j=i+1;j<n;j++){ if(hn[j].way<hn[k].way) k=j; } if(k>i){ temp = hn[i]; hn[i] = hn[k]; hn[k] = temp; } } }//将走法的数量进行排序,将最少的走法放在数组的头;void dfs(int x,int y,intcount){ int i,tx,ty; manode[] t = new manode[N]; if(count >N*N){ output(); return; } //当count计数器超过64时,打印输出;for(i=0;i<N;i++){ tx = x+fx[i]; ty = y+fy[i]; manode h = new manode(); t[i]=h; t[i].x = tx; t[i].y = ty; t[i].way = wayout(tx,ty); } sort(t,N); for(i = 0;t[i].way<0;i++) ; for(;i<N;i++){ tx = t[i].x; ty = t[i].y; board[tx][ty] = count; dfs(tx,ty,count+1); board[tx][ty] = 0;//遇到死路时,回退回去,并将其变成0; } }//深度搜索与回溯算法;publicstaticvoid main(String[] args) { int x,y; Scanner input = new Scanner(System.in); System.out.println("please input x,y:"); x = input.nextInt(); y = input.nextInt(); ma test = new ma(); board[x][y]=1; test.dfs(x, y, 2); } void output(){ for(int i = N-1;i>=0;i--){ for(int j = 0;j<N;j++){ System.out.printf("%d\t",board[i][j]); } System.out.printf("\n\n\n"); } System.exit(0); } //打印输出函数;}