---
tags: 演算法, 110-2
---
# 演算法作業 HW10
- 本週進入到第5章後半，樹搜尋延伸至A*演算法。
# 觀念題 :book:
## 第1題: 01背包問題
- 已知有六個物品，其價值和重量如下，背包重量限制為34。
- 仿照課本以tree search來解。
- 請將下圖中的框框中，填入其upper bound與lower bound

## 第2題: A* 解multi-stage shortest path problem
- 請使用A* 找出S到T的最短路徑。請畫出樹狀圖，並標示各點的cost，並註明哪裏分枝不用再繼續尋找了。

## 第3題: Channel Routing Problem
- 請使用A* 解Channel Routing Problem。
- 本題將原本題目的net 7移除，只剩下7個nets，請找出最少track的安排方式。

# 程式題: :computer:
- 主題：[Breadth-First Search](https://leetcode.com/tag/breadth-first-search/)
## 第4題: 合併二元樹
- [Merge Two Binary Trees - LeetCode](https://leetcode.com/problems/merge-two-binary-trees/)
- 題目：給定二個二元樹，請建立一個合併兩者的二元樹
- 這題可以用DFS也可用BFS，都可以試試看。
## 第5題: 最深葉子的最低共同祖先
- [Lowest Common Ancestor of Deepest Leaves - LeetCode](https://leetcode.com/problems/lowest-common-ancestor-of-deepest-leaves/)
- 所謂Lowest Common Ancestor(最低共同祖先)，舉例來說，下圖中xy的最低共同祖先就是深綠色的點。
- 若當只有一個點時，該點的LCA就是自己。
- 例如x的最低共同祖先就是x。
- 
- 題目：給定一個二元樹，找出該二元樹最深的葉子之最低共同祖先
- 建議以BFS來作。
- 例如下圖中，最深的葉子為7,4,而LCA就是2。
- 
## 第6題:
- [Binary Tree Pruning - LeetCode](https://leetcode.com/problems/binary-tree-pruning/description/)
- 題目：給定一個二元樹，刪除不含1的子樹

## 第7題 : 心得
- 請在以下表單填寫對本週(hw10)影片教學和程式作業的問題/收穫/適應程度/心得。
- [https://forms.gle/3FqW22n3ViN98jbZ9](https://forms.gle/3FqW22n3ViN98jbZ9)