基本要素

贪心选择

最优子结构

1. 建立数学模型来描述问题；
2. 把求解的问题分成若干个子问题；
3. 对每一子问题求解，得到子问题的局部最优解；
4. 把子问题的解局部最优解合成原来解问题的一个解。

• 随着算法的进行，将积累起其它两个集合：一个包含已经被考虑过并被选出的候选对象，另一个包含已经被考虑过但被丢弃的候选对象。
• 有一个函数来检查一个候选对象的集合是否提供了问题的解答。该函数不考虑此时的解决方法是否最优。
• 还有一个函数检查是否一个候选对象的集合是可行的，也即是否可能往该集合上添加更多的候选对象以获得一个解。和上一个函数一样，此时不考虑解决方法的最优性。
• 选择函数可以指出哪一个剩余的候选对象最有希望构成问题的解。
• 最后，目标函数给出解的值。
• 为了解决问题，需要寻找一个构成解的候选对象集合，它可以优化目标函数，贪婪算法一步一步的进行。起初，算法选出的候选对象的集合为空。接下来的每一步中，根据选择函数，算法从剩余候选对象中选出最有希望构成解的对象。如果集合中加上该对象后不可行，那么该对象就被丢弃并不再考虑；否则就加到集合里。每一次都扩充集合，并检查该集合是否构成解。如果贪婪算法正确工作，那么找到的第一个解通常是最优的。

背包问题

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);
    }       //打印输出函数；
}