假設(shè)有7個(gè)物品，它們的重量和價(jià)值如下表所示。若這些物品均不能被分割，且背包容量M＝150，使用回溯方法求解此背包問(wèn)題。請(qǐng)寫(xiě)出狀態(tài)空間搜索樹(shù)。

對(duì)于下圖使用Dijkstra算法求由頂點(diǎn)a到其他各個(gè)頂點(diǎn)的最短路徑。并給出求各個(gè)頂點(diǎn)對(duì)之間的最短路徑的算法思想。

排序和查找是常用的計(jì)算機(jī)算法。按照要求完成下題：
（1）對(duì)數(shù)組A={15，9，115，118，3，90，27，25，5}，使用合并排序方法將其排成遞減序。
（2）若改變二分搜索法為三分搜索法，即從一個(gè)遞減序列A中尋找元素Z，先與元素比較，若比較，若，則在前面[n/3]個(gè)元素中尋找Z；否則與比較，總之使余下的序列為[n/3]個(gè)元素。給出該方法的偽代碼描述。
（3）使用上述算法對(duì)（1）所得到的結(jié)果搜索如下元素，并給出搜索過(guò)程：118，31，25。