十分钟了解算法（2）——初始贪心算法和动态规划_贪心初始化

1. 贪心算法

（一）贪心的本质：

为了达到目的，每一步都采取最优的方法，也就是局部最优解，从而得到全局最优解。

（二）贪心的特点：

1. 往往不能得到最优解，只有近似解。
2. 简单粗暴，速度快。

（三）贪心求解的步骤：

1. 从条件中找出使得利益最大化的最值
2. 不断扩大规模，继续找最值

（四）贪心适合的问题：

NP完全问题：

定义：问题涉及序列 / 集合，需要计算所有的解并从中选出最小/最短的那个。

特点：

• 元素较少时算法的运行速度非常快，但随着元素数量的增加，速度会变得非常慢。
• 不能将问题分成小问题，必须考虑各种可能的情况。

例子：

1. 活动安排问题：

设有n个活动，其中每个活动都要求使用同一资源，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si<fi。如果选择了活动i，则它在区间[si，fi]内占用资源。若区间[si，fi]与区间[sj，fj]不相交，则称活动i与活动j是相容的。也就是说，当sj≥fi或si≥fj时，活动i与活动j相容。

解决：每次都贪心的选择结束时间最早的活动，就可以办最多的活动。先选择结束时间最早的那一个活动，然后往后依次查找结束时间最早的并且与上一个活动不冲突的活动加入。

    //先对活动开始时间进行排序
    public static void sort(int[] start, int[] end) {
        for (int i = 1; i < start.length; i++) {
            if (start[i] < start[i - 1]) {
                int j = i - 1;
                int temp1 = start[i];
                int temp2 = end[i];
                for (; j >= 0 && start[j] > temp1; j--) {
                    start[j + 1] = start[j];
                    end[j + 1] = end[j];
                }
                start[j + 1] = temp1;
                end[j + 1] = temp2;
            }
        }
    }

    public static void getActivity(int[] start, int[] end, ArrayList<Integer> selected) {
        int endTime = Integer.MAX_VALUE;
        int index = -1;
        for (int i = 0; i < end.length; i++) {  //确定时间结束最早的活动
            if (endTime > end[i]) {
                index = i;                  //记录活动
                endTime = end[i];           //记录结束时间
            }
        }
        selected.add(index);            
        for (int i = start[selected.get(0)]; i < start.length; i++) {   //从第一个活动开始
            if (start[i] >= endTime) {        //活动开始时间必须比上个活动的时间晚，不能发生冲突
                endTime = end[i];            //初始化下一个活动的结束时间
                index = i;                  //初始化下一个活动
                for (int j = i; j < end.length; j++){
                    if(end[j] < endTime)    //寻找在开始时间之后最早结束的活动
                    {
                        endTime = end[j];
                        index = j;
                    }
                }
                selected.add(index);        //记录活动
            }
        }
    }
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

2. 最优装载问题：

有一批集装箱要装上一艘载重量为c的轮船。其中集装箱i的重量为Wi。求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。

解决：每次都贪心的选择装最轻的集装箱，就可以装最多。

  // 最优装载问题
    public static int load(float[] weight, float maxWeight) {
        Arrays.sort(weight);    //先对重量排序
        int index = 0;
        int sum = 0;
        while (sum < maxWeight){
            sum += weight[index++]; //每次选择重量最小的货物
        }
        sum -= weight[index-1];
        return sum;
    }
1
2
3
4
5
6
7
8
9
10
11

3. 背包问题:

有N件物品和一个容量为Height的背包。第i件物品的重量是height[i]，价值是value[i]。可以选择装入物品i的一部分，求解怎么把物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。

解决：求每个物品的价值重量比，即价值/重量。然后每次都贪心的添加价值重量比最大的物品。

4. 多机调度问题：

给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。

解决：每次都贪心的选择最长处理时间作业。将n个作业依其所需的处理时间从大到小排序。然后依此顺序将作业分配给空闲的处理机。

2. 动态规划

（一）动态规划的原理：

先解决子问题，再根据子问题解决大问题

（二）动态规划的特点：

• 在给定约束条件下找到最优解
• 问题可分解为彼此独立且离散的子问题

（二）动态规划求解步骤：

1. 确定约束条件和优化值，将需要优化的值当做单元格，根据优化值确定坐标轴。
2. 划分问题：把问题由上到下划分，每个单元格都是子问题。
3. 分别解决子问题。
4. 解决大问题。

（二）动态规划适合的问题：

01背包问题：

有N件物品和一个容量为Height的背包。第i件物品的重量是height[i]，价值是value[i]。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。

1. 约束条件是背包的容量，需要优化的是背包的总价值。所以单元格是背包的价值，如果需要确定价值，那么首先需要每个物品的价值，然后还需要知道背包的容量，做约束条件。
2. 划分子问题：分别装入物品，计算此时背包的价值。
3. 解决子问题：根据新增加的目标和之前的数据，确定取该物品和不取该物品哪个价值更大，也就是取上一个单元格的价值（cell[i-1][j]） 和 当前商品和剩余空间的总价值（v[i]+cell[i-1][j-w[i]]） 之间的最大值。选择满足每一列约束条件的最大的目标及其权值添加进表格。
4. 最后一个表格就是整个问题的最优解

//01背包问题
    public static int getBag(int maxWeight,int[] weight,int[] value){
        int weightLen = maxWeight;  //用背包的容量作为表格的列
        int valueLen = value.length;//用物品的数量作为表格的行
        int maxValue = 0;           //记录最大权值
        int[][] bag = new int[valueLen][weightLen];     //用表格记录背包
        for (int i = 0; i < valueLen; i++) { 
            for (int j = 0; j < weightLen; j++) {
                if (i == 0) {                           //第一行
                    if(weight[i] <= j+1)                //如果重量比背包小，那就可以装进去
                        bag[i][j] = value[0];           
                    else
                        bag[i][j] = 0;                  //否则，背包装不进去，只能为0
                }
                else {
                    if (weight[i] > j+1)              //如果重量比背包大，那么装不进去
                        bag[i][j] = bag[i - 1][j];    //背包只能取之前装过的最大价值
                    else if(weight[i] == j+1)     	 //如果重量和背包相同
                        bag[i][j] = Math.max(bag[i - 1][j],value[i]); //那么就看装这件东西划算，还是不装这件东西装别的东西划算
                    else                       	  //如果重量比背包小
                        bag[i][j] = Math.max(bag[i - 1][j], bag[i - 1][j - weight[i]] + value[i]);  //那么可以装进背包，看看拿出一些东西腾出空间来装这个东西之后的价值大
                                                                                                    // 还是不装之前的总价值大
                }
                maxValue = bag[i][j];           	//找到当前最大价值了
            }
        }
        for (int i = 0; i < bag.length; i++) {       //看看表格最后的结果
            for (int j = 0; j < bag[i].length; j++) {
                System.out.printf("%d ",bag[i][j]);
            }
            System.out.printf("%n");
        }
        return maxValue;
    }

    public static void main(String[] args) {
        int maxWeight = 4;
//        int[] weight = {1,4,3};
//        int[] value = {1500,3000,2000};
        int[] weight = {4,3,1};
        int[] value = {3000,2000,1500};
//        String[] goods = {"音响","笔记本电脑","吉他"};
        System.out.println(getBag(maxWeight,weight,value));
    }
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

最长公共子串：

找出两个单词之间的最长公共子串。

1. 约束条件是每个单词的每个字符，需要优化的是两个单词间含有的公共最多连续的字符。所以单元格是两个单词此时的最长公共子串数量，如果需要确定最长公共子串，那么就需要比较两个单词，因此两个单词分别是行和列。
2. 划分子问题：分别计算每个字符加入后，此时两个字符串的最长公共子串。
3. 解决子问题：根据新增加的字符和之前的子串，如果新增加的字符相同，就在之前子串的基础上再添加字符，如果新增加的字符不同，就需要清零。也就是0 和 当前字符+之前字符的字符数（v[i]+cell[i-1][j-1]） 之间的最大值。选择满足约束条件的最大的目标及其字符数添加进表格。
4. 解决大问题：表格中的最大值就是问题的解。

 //公共最长子串
    public static int subString(char[] a, char[] b) {
        int len1 = a.length;
        int len2 = b.length;
        int[][] strs = new int[len1][len2];         //记录动态规划的过程
        int max = 0;
        for (int i = 0; i < len1; i++) {            //以字符串1为行
            for (int j = 0; j < len2; j++) {        //以字符串2为列
                if (i == 0 || j == 0) {
                    if (a[i] == b[j])    //首行表示用字符串1的第一个字符比较字符串2，如果相同，则初始化为1，否则初始化为0
                        strs[i][j] = 1; //首列表示字符串2的第一个字符被字符串1比较，如果相同，则初始化为1，否则初始化为0
                    else                
                        strs[i][j] = 0;
                } else {
                    if (a[i] == b[j])   //如果字符串中的字符相同，则是前面公共子串的长度+1
                        strs[i][j] = strs[i - 1][j - 1] + 1;
                    else                //字符不同，则初始化为0
                        strs[i][j] = 0;
                }
                if (strs[i][j] > max)   //结果为表中最大长度
                    max = strs[i][j];
            }
        }
        for (int i = 0; i < strs.length; i++) {
            for (int j = 0; j < strs[i].length; j++) {
                System.out.printf("%d ", strs[i][j]);
            }
            System.out.printf("%n");
        }
        return max;
    }
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
28
29
30
31

最长公共子序列：

找出两个单词之间的最长公共子序列，只需要在序列中即可。

1. 约束条件是每个单词的每个字符，需要优化的是两个单词间含有的公共最多字符。所以单元格是两个单词此时的最长公共子序列的数量，如果需要确定最长公共子序列，那么就需要比较两个单词，因此两个单词分别是行和列。
2. 划分子问题：分别计算每个字符加入后，此时两个字符串的最长公共子序列。
3. 解决子问题：根据新增加的字符和之前的子序列，如果新增加的字符相同，就在之前子序列的基础上再添加字符，如果新增加的字符不同，就取上一次的最长子序列，没必要清零。也就是上一次的子序列最大值（max（cell[i-1][j],cell[i][j-1]）） 和 当前字符+之前字符的字符数（v[i]+cell[i-1][j-1]） 之间的最大值。选择满足约束条件的最大的目标及其字符数添加进表格。
4. 解决大问题：表格中的最大值就是问题的解。

   //公共最长子序列
    public static int subList(char[]a,char[]b){
        int len1 = a.length;
        int len2 = b.length;
        int[][] strs = new int[len1][len2];         //记录动态规划的过程
        int max = 0;
        for (int i = 0; i < len1; i++) {            //以字符串1为行
            for (int j = 0; j < len2; j++) {        //以字符串2为列
                if (i == 0 || j == 0) {
                    if (a[i] == b[j])    //首行表示用字符串1的第一个字符比较字符串2，如果相同，则初始化为1，否则初始化为0
                        strs[i][j] = 1; //首列表示字符串2的第一个字符被字符串1比较，如果相同，则初始化为1，否则初始化为0
                    else
                        strs[i][j] = 0;
                } else {
                    if (a[i] == b[j])   //如果字符串中的字符相同，则是前面最长公共子序列的长度+1
                        strs[i][j] = Math.max(strs[i - 1][j],strs[i][j - 1])+1;
                    else                //字符不同，则是前面最长公共子序列的长度
                        strs[i][j] = Math.max(strs[i - 1][j],strs[i][j - 1]);
                }
                if (strs[i][j] > max)   //结果为表中最大长度
                    max = strs[i][j];
            }
        }
        for (int i = 0; i < strs.length; i++) {
            for (int j = 0; j < strs[i].length; j++) {
                System.out.printf("%d ", strs[i][j]);
            }
            System.out.printf("%n");
        }
        return max;
    }
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
28
29
30
31