哈夫曼樹

一般的，a、b、c、d、e、f、g七個(gè)字符在一份數(shù)據(jù)中出現(xiàn)的次數(shù)為1、2、3、4、5、6、7。

step1：將7個(gè)字符中，出現(xiàn)此次最少的字符a和b取出，構(gòu)造一根子樹x，它們的次數(shù)分別成為左右節(jié)點(diǎn)，它們的次數(shù)和組成根節(jié)點(diǎn)。

step2：將step1的到樹放入原數(shù)據(jù)中（x，c，d，e，f，g），將此時(shí)數(shù)據(jù)中出現(xiàn)次數(shù)最少的兩個(gè)取出（x和c），構(gòu)造一根新的子樹y，它們的次數(shù)分別成為左右節(jié)點(diǎn)，它們的次數(shù)和組成根節(jié)點(diǎn)。

...

重復(fù)step2，直到只剩下一個(gè)根節(jié)點(diǎn)的樹，即為哈夫曼樹。

哈夫曼編碼

將哈夫曼樹所有子樹的左子樹路徑標(biāo)0.，右子樹路徑標(biāo)1，依次求出各個(gè)字符的編碼。

裝箱問題的求解

離散數(shù)學(xué)的最優(yōu)組合，一般通過(guò)動(dòng)態(tài)規(guī)劃實(shí)現(xiàn)。

無(wú)法求得最優(yōu)解，一般是近似解（貪心（婪）算法）。

例如沙袋問題：如何用盡可能少的箱子裝下大小不一的沙袋。

將沙袋排序，最大沙袋先入，然后從隊(duì)列尾部取最小的沙袋入，如果箱子未裝滿繼續(xù)隊(duì)尾，否則下一個(gè)隊(duì)首和隊(duì)尾。