哈夫曼树
一般的,a、b、c、d、e、f、g七个字符在一份数据中出现的次数为1、2、3、4、5、6、7。
step1:将7个字符中,出现此次最少的字符a和b取出,构造一根子树x,它们的次数分别成为左右节点,它们的次数和组成根节点。
step2:将step1的到树放入原数据中(x,c,d,e,f,g),将此时数据中出现次数最少的两个取出(x和c),构造一根新的子树y,它们的次数分别成为左右节点,它们的次数和组成根节点。
...
重复step2,直到只剩下一个根节点的树,即为哈夫曼树。
哈夫曼编码
将哈夫曼树所有子树的左子树路径标0.,右子树路径标1,依次求出各个字符的编码。
装箱问题的求解
离散数学的最优组合,一般通过动态规划实现。
无法求得最优解,一般是近似解(贪心(婪)算法)。
例如沙袋问题:如何用尽可能少的箱子装下大小不一的沙袋。
将沙袋排序,最大沙袋先入,然后从队列尾部取最小的沙袋入,如果箱子未装满继续队尾,否则下一个队首和队尾。