贪心算法_贪心算法的难点

贪心算法

求解问题时，总是做出当前看来最好的选择。
但是贪心算法最难的是要证明每一步的贪心选择能够得出最终的最优解。
第二难点是如何贪心

均分纸牌

有N堆纸牌，编号1，2 ,3 。。。N。每堆上有若干张，但纸牌的总数必为N的倍数。可以在任一堆上取若干张纸牌，然后移动。移动规则如下：

• 在编号为1上取得纸牌只能移动到编号为2的堆上；
• 在编号为N上取得纸牌只能移动到编号为N-1的堆上；
• 其他位置，只能移动到相邻的堆上

算法分析：设a[i]为第i堆纸牌的张数(0 <= i <= N)，v为均分后每堆纸牌的张数，s为最小移动次数。
按照从做到右的顺序移动纸牌。如第i堆纸牌数不等于平均值，则移动一次

• 若a[i] > v，则将a[i]-v张从第i堆移动到第i+1堆
• 若a[i] < v，则将v-a[i]张从第i+1堆移动到第i堆。

以上两种情况可以合并为一种，将a[i]-v从第i堆移动到i+1堆。

import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int N = sc.nextInt();
            int[] card = new int[N];
            int avg = 0;
            int s = 0; //记录移动次数
            for(int i=0; i<N; i++){
                card[i] = sc.nextInt();
                avg += card[i];
            }
            avg = avg / N;
            for(int i=0; i<N-1; i++){
                //有几个不等于均值，移动几次，这样就不用算了，直接统计就好了
                if(card[i] != avg){
                    s++;
                    card[i+1] = card[i+1] + (card[i] - avg);
                    card[i] = avg;
                }
            }
            System.out.println(s);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

最大拼接整数

给出n个整数，将它们连接成一排，组成一个最大的整数
将数字转换为字符串，比较 a+b 和 b+a

import java.util.Arrays;
import java.util.Scanner;
import java.util.Comparator;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
             String[] word = sc.nextLine().split(" ");
             Arrays.sort(word, new Comparator<String>(){
                //返回-1，代表就按照参数的循序排
                @Override
                int compare(String o1, String o2){
                    String o1o2 = o1+o2;
                    String o2o1 = o2+o1;
                    if(o1o2.compareTo(o2o1) > 0) return -1;
                    else return 1;
                }
                });

            StringBuilder sb = new StringBuilder();
            for(int i=0; i<word.length; i++){
                sb.append(word[i]);
            }
            System.out.println(sb.toString());
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

其他例子

• 最小生成树Prim算法
• Kruskal算法

参考来源

http://blog.sina.com.cn/s/blog_5fe1eed50100ejez.html