算法——贪心和动态规划

引言

本文整理了常见的动态规划和贪心的相关算法，方便以后查阅。算法相关的文章均收录于<算法系列文章>。

动态规划

切割钢条问题

package bbm.dp;

/**
 * Serling 公司购买长钢条, 将其切割为短钢条出售。切割工序本身没有成本支出。公司管理层希望知道最佳的切割方案。
 * 假定我们知道 Seling 公司出售一段长度为 i 英寸的钢条的价格为P(i=1,2,⋯,单位为美元)。钢条的长度均为整英寸。下图图给出了一个价格表的样例。
 * 长度i: 1  2  3  4   5   6   7   8   9   10
 * 价格p: 1  5  8  9  10  17   17  20  24  30
 *
 * 本例采用动态规划方案，自底向下的求解各个子问题，并记录子问题的解，然后逐步的计算出原问题的解
 *
 * @author bbm
 */
public class CutRod {
    int[] price = new int[] {0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30};

    public void cutRod(int n) {
        int[] bestSum = new int[n + 1];
        int[] bestCutSize = new int[n + 1];
        bestSum[0] = 0;
        for (int j = 1; j <= n; j++) {
            int q = Integer.MIN_VALUE;
            for (int i = 1; i <= j; i++) {
                if (q < price[i] + bestSum[j - i]) {
                    q = price[i] + bestSum[j - i];
                    bestCutSize[j] = i;
                }
            }
            bestSum[j] = q;
        }
        print(bestSum);
        print(bestCutSize);
        while (n > 0) {
            System.out.println(bestCutSize[n]);
            n = n-bestCutSize[n];
        }
    }

    void print(int[] nums) {
        for (int num : nums) {
            System.out.print(num + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        new CutRod().cutRod(7);
    }
}

最大公共子序列

package bbm.dp;

import java.util.ArrayList;

/**
 * 最大公共子序列：例如，ABCD 和 ACE 这两个序列的最大公共子序列为 AC
 * 本例中采用动态规划的思想，从两个序列的头出发x[i], y[j]，如果 x[i] y[j] 相等，那么到 x[i] y[j] 的最大公共子序列就比 x[i-1] y[j-1]
 * 多 1，如果他们不相等，那么就要检查 x[i-1] y[j] 和 x[i] y[j-1] 为止哪边的子序列最大，让 x[i] y[j] 也等于该值，当 i j 达到 x y 的
 * 末尾时，我们就得到了最大公共子序列
 * @author bbm
 */
public class LongestCommonSubSequence {

    public ArrayList<Character> lcsLength(char[] x, char[] y) {
        char[][] path = new char[x.length + 1][y.length + 1];
        int[][] length = new int[x.length + 1][y.length + 1];
        for (int i = 0; i < x.length; i++) {
            for (int j = 0; j < y.length; j++) {
                if (x[i] == y[j]) {
                    length[i + 1][j + 1] = length[i][j] + 1;
                    path[i + 1][j + 1] = '↖';
                } else if (length[i][j + 1] > length[i + 1][j]) {
                    length[i + 1][j + 1] = length[i][j + 1];
                    path[i + 1][j + 1] = '↑';
                } else {
                    length[i + 1][j + 1] = length[i + 1][j];
                    path[i + 1][j + 1] = '←';
                }
            }
        }
        System.out.print(' ');
        System.out.print(' ');
        for (char c : y) {
            System.out.print(c);
            System.out.print(' ');
            System.out.print(' ');
        }
        System.out.println();
        for (int i = 1; i < path.length; i++) {
            System.out.print(x[i - 1]);
            System.out.print(' ');
            for (int j = 1; j < path[i].length; j++) {
                System.out.print(path[i][j]);
                System.out.print(length[i][j]);
                System.out.print(' ');
            }
            System.out.println();
        }
        ArrayList<Character> result = new ArrayList<>();
        getPath(result, x, path, x.length, y.length);
        return result;
    }

    private void getPath(ArrayList<Character> result, char[] x, char[][] path, int i, int j) {
        if (i == 0 || j == 0) {
            return;
        }
        if (path[i][j] == '↖') {
            getPath(result, x, path, i - 1, j - 1);
            result.add(x[i - 1]);
        } else if (path[i][j] == '↑') {
            getPath(result, x, path, i - 1, j);
        } else {
            getPath(result, x, path, i, j - 1);
        }
    }

    public static void main(String[] args) {
        ArrayList<Character> result = new LongestCommonSubSequence()
            .lcsLength(new char[] {'a', 'b', 'c', 'b', 'd', 'a', 'b'}, new char[] {'b', 'd', 'c', 'a', 'b', 'a'});
        System.out.print("LCS: ");
        for (char c : result) {
            System.out.print(c);
        }
        System.out.println();
    }

}

最大子序列问题

package bbm.dp;

/**
 * 这里我们用动态规划的思想重新解最大子序列的问题
 *
 * @author bbm
 */

public class DPMaxSubSequence {
    public int maxSubArray(int[] nums) {
        if (nums == null) {
            return 0;
        }
        if (nums.length == 1) {
            return nums[0];
        }
        // end 记录了以 i 为结尾的序列中最大的子序列和
        int[] end = new int[nums.length];
        end[0] = nums[0];
        int max = end[0];
        for(int i = 1; i < nums.length; i++) {
            if (nums[i] > end[i - 1]) {
                if (end[i-1] > 0) {
                    end[i] = end[i - 1] + nums[i];
                } else {
                    end[i] = nums[i];
                }
            } else {
                end[i] = end[i - 1] + nums[i];
            }
            if (end[i] > max) {
                max = end[i];
            }
        }
        return max;
    }

    public static void main(String[] args) {
        DPMaxSubSequence maxSubSequence = new DPMaxSubSequence();
        int result = maxSubSequence.maxSubArray(new int[] {-2, -1, 1 ,1, 4, -3, -4, 3});
        System.out.println(result);
    }
}

0-1 背包问题

package bbm.dp;

/**
 * 0-1背包问题：给定一组多个物品，每种物品都有自己的重量和价值，在限定的总重量/总容量内，选择其中若干个（也即每种物品可以选0个或1个），
 * 设计选择方案使得物品的总价值最高。
 *
 * 动态规划的思路是：逐渐的增加商品数量和背包容量
 * 1. 如果新增的商品重量比当前背包容量大，把新增的商品排除掉，重新算总价值
 * 2. 如果新增的商品重量比当前背包容量小，比较如下两种情况哪个总价值更高，选择总价高的那个方案：
 *      2.1 新增的商品排除掉，重新算总价值
 *      2.2 将新增商品放入包内，计算 （新商品 price + 剩余商品在剩下的容量下的最高价值）
 * @author bbm
 */
public class KnapsackProblem {

    public int findBestSolution(int[] price, int[] weight, int maxWeight) {
        int itemCount = price.length;
        int[][] memo = new int[itemCount + 1][maxWeight + 1];
        int max = Integer.MIN_VALUE;
        for (int i = 1; i <= itemCount; i++) {
            for (int j = 1; j <= maxWeight; j++) {
                if (weight[i - 1] > j) {
                    memo[i][j] = memo[i - 1][j];
                } else {
                    memo[i][j] = Math.max(memo[i - 1][j], price[i - 1] + memo[i - 1][j - weight[i - 1]]);
                }
            }
            if (memo[i][maxWeight] > max) {
                max = memo[i][maxWeight];
            }
        }
        System.out.print("\t");
        for (int i = 0; i <= maxWeight; i++) {
            System.out.print(i + "\t");
        }
        System.out.println();
        for (int i = 0; i < memo.length; i++) {
            System.out.print(i + "\t");
            for (int j = 0; j < memo[i].length; j++) {
                System.out.print(memo[i][j] + "\t");
            }
            System.out.println();
        }
        System.out.println();
        return max;
    }

    public static void main(String[] args) {
        int maxPrice = new KnapsackProblem().findBestSolution(new int[] {1, 6, 18, 22, 28},
            new int[] {1, 2, 5, 6, 7}, 11);
        System.out.println(maxPrice);
    }
}

贪心算法

活动选择

package bbm.greedy;

import java.util.ArrayList;
import java.util.List;

/**
 * 活动选择问题：已知一些活动的开始时间和结束时间，计算怎么安排活动能让尽可能多的活动互不重叠。
 * activity 0  1  2  3  4  5  6  7  8  9  10
 * start    1  3  0  5  3  5  6  8  8  2  12
 * end      4  5  6  7  9  9 10 11 12 14  16
 * 这里我们已经对 end time 进行了排序，而 end time 最小的值肯定会出现在最优解中，如果最优解的第一个活动 end time >= activity 0 的 end time
 * 那么我们完全可以用 activity 0 来替换最优解的第一个活动，而如果最优解的第一个活动是 end time < activity 0 的 end time，这并不会发生，因为
 * activity 0 的 end time 就是最小了。
 *
 * 基于上述规律，我们可以利用贪心算法，按照 end time 递增的顺序遍历所有 activity 如果 activity 的 start end 大于最优活动集的所有活动的 end time
 * 那么我们就将这个新活动加入到 最优活动集，重复该过程知道遍历完所有活动，我们就得到了最终的最优活动集
 * @author bbm
 */
public class ActivitySelector {
    public List<Integer> activitySelector(int[] start, int[] end) {
        List<Integer> result = new ArrayList<>();
        result.add(0);
        int lastEnd = end[0];
        for (int i = 1; i < start.length; i++) {
            if (start[i] > lastEnd) {
                result.add(i);
                lastEnd = end[i];
            }
        }
        return result;
    }

    public static void main(String[] args) {
        List<Integer> result = new ActivitySelector().activitySelector(new int[] {1, 3, 0, 5, 3, 5, 6, 8, 8, 2, 12},
            new int[] {4, 5, 6, 7, 9, 9, 10, 11, 12, 14, 16});
        for (int i : result) {
            System.out.print(i);
            System.out.print(' ');
        }
        System.out.println();
    }
}

哈夫曼编码

package bbm.greedy;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

/**
 * 哈夫曼编码根据字符出现的频率来规划每个字符使用什么编码，它将构建一个二叉树，出现频率越高的字符越接近树根，然后从根节点数出发，当经过左节点
 * 时记录编码值0，当经过右节点时记录编码值1，按照这样的规则，从根节点到任意实际字符节点所记录的所有编码值，就是该字符的编码，例如
 *     &
 *    /\
 *   &  c
 *  /\
 * a  b
 * 上树中， a 的编码就是 00，b 的编码是 01，c 的编码是 1
 *
 * 那么怎么构建上面这棵编码树呢，我们可以采用贪心的思路，
 * 1. 先对所有字符创建其对应的树节点，得到一个节点集合 nodes，
 * 2. 然后根据所有字符出现的频率，每次拿出节点集合 nodes 中频率最低的两个节点，为它们创建一个父节点，并将父节点放入 nodes 中
 * 3. 重复该过程直到 nodes 中只含有一个节点时，该节点就是树根 root 节点
 * @author bbm
 */
public class Huffman {

    public Node encode(char[] chars, int[] frequencies) {
        List<Node> nodes = new ArrayList<>();
        for (int i = 0; i < chars.length; i++) {
            nodes.add(new Node(frequencies[i], chars[i]));
        }
        nodes.sort(Comparator.comparingInt(o -> o.freq));
        while (nodes.size() > 1) {
            Node left = nodes.remove(0);
            Node right = nodes.remove(0);
            Node newNode = new Node(left.freq + right.freq, '&');
            newNode.left = left;
            newNode.right = right;
            nodes.add(newNode);
            nodes.sort(Comparator.comparingInt(o -> o.freq));
        }
        return nodes.get(0);
    }

    public static void main(String[] args) {
        Node result = new Huffman().encode(new char[] {'f', 'e', 'c', 'b', 'd', 'a'}, new int[] {5, 9, 12, 13, 16, 45});
        result.print(0);
    }

    public static class Node {
        int freq;
        char ch;
        Node left;
        Node right;

        public Node(int freq, char ch) {
            this.freq = freq;
            this.ch = ch;
        }

        public void print(int depth) {
            for (int i = 0; i < depth; i++) {
                System.out.print('-');
            }
            System.out.println(ch + ":" + freq);
            if (left != null) {
                left.print(depth + 1);
            }
            if (right != null) {
                right.print(depth + 1);
            }
        }
    }
}

参考内容

[1] 《算法导论》
[2] 0-1背包问题的动态规划算法