1、貪心算法山東師大附中陳鍵飛貪心貪心法是沿著一種固定的策略一直走下去的算法與動態(tài)規(guī)劃和搜索的區(qū)別是，動態(tài)規(guī)劃和搜索在一個階段都會考慮所有可能出現(xiàn)的狀態(tài)，而貪心只需要知道哪個狀態(tài)是最優(yōu)可以用貪心的條件是滿足：每步都最優(yōu)，總結果也最優(yōu)小例子部分背包問題：有一個容量W的背包，有N種物品，每種有Wi單位的體積和Vi單位的價值你可以把一件物品的一部分裝進背包，怎么使總價值最大？01不能W=9W1=7 , V1 = 14W2=5 , V2 = 9W3=4 , V3 = 7例題1有n個人, 第i個人重量為wi。每艘船的載重量均為C, 最多乘兩個人。用最少的船裝載所有人。讓最輕的人和能坐下的最重的人坐例題2有1

2、N的一個排列，每次可以交換任意兩個，用最少的次數(shù)將它們變成1N過河有N個人要過一個河，有一個最多載兩人的小船，每個人有一個過河時間，如果兩個人過河，則用時是較慢的那個人的用時，問最少需要多長時間所有人都過河。如A,B,C,D 1,2,5,8AB2 A1AC5 A1AD8AB2 A1C D 8 B 2A B 2區(qū)間上的問題有N個區(qū)間，選擇最多的區(qū)間，使它們不互相重疊區(qū)間上的問題有N個閉區(qū)間，選最少的點，使得每個區(qū)間都至少包含一個點有N個閉區(qū)間，選最少的整點，使得每個區(qū)間都至少包含k個點區(qū)間上的問題有N個閉區(qū)間Ai,Bi，選最少的區(qū)間覆蓋一條指定線段S,THuffman編碼給定N個字符每個字符的出

3、現(xiàn)頻率Ci，給每個字符編一個二進制碼，不能有一個字符的編碼是另一個的前綴。問編碼后的文本最短多長。如aaaabbbc則a=0，b=10，c=11則 Huffman編碼Huffman樹怎樣構造？每次取出現(xiàn)頻率最低的兩個字符將它們的編碼一個在最后加上0，一個加上1然后合并成同一個abc0101Huffman編碼Ca=9 , Cb=5 , Cc=10 , Cd=1 , CE=6 , CF=10abcdef9510166Huffman編碼需要證明什么？頻率最小的兩個點一定是兄弟，且深度最大為什么深度最大的點一定有兄弟？每個點一定有兩個兒子合并果子有N堆果子，每堆重量是Wi，合并兩堆果子i/j的費用是Wi+Wj，用最小的費用合并所有果子流水作業(yè)調(diào)度問題有n個作業(yè)要在兩臺機器M1和M2組成的流水線上完成加工。每個作業(yè)i都必須先花時間ai在M1上加工，然后花時間bi在M2上加工。確定n個作業(yè)的加工順序，使得從第一個作業(yè)在機器M1上加工開始到最后一個作業(yè)在機器M2上加工為止總時間最少。流水作業(yè)調(diào)度問題直觀上看，應該讓M1不停地工作，而M2的空閑時間盡量少設N1為a b的作業(yè)集合，N2為a b的作業(yè)集合將N1中的作業(yè)照a非減序排序，N2中的作業(yè)按照b非增序排序，則N1作業(yè)接N2作業(yè)構成最優(yōu)順序。一個