---
tags: 演算法, 110-2
---
# 演算法作業 HW7
本週程式題的難度漸漸提升。
這次主題是Ch4 Divide and Conquer。這類程式常用遞迴的方式來寫。
另外，有使用到資料結構裏的linked list與tree。若不清楚，請復習一下。
# 觀念題 :book:

## 第1題: knapsack problem背包問題(Ch3)
有四件物品，編號由1到4，物品重量依序為20,40,10,30。物品價值依序為100,60,30,60。背包最大限重為80。請說明要放哪些東西(可以放部分)，可以讓背包內物品價值總合最大。
## 第2題: Closest Pair Problem
請說明Closest Pair Problem，每回合的合併過程？(可參考PPT13頁)
## 第3題: Convex Hull Problem
請說明Convex Hull Problem，
(1)為何不直接用sort來得到polygon，而要採用merge？
(2)請說明如何將polygon，修改成convex hull？

## 程式題:[Divide and Conquer](https://leetcode.com/tag/divide-and-conquer/)

## 第4題: 將linked list的數列排序
[Sort List - LeetCode](https://leetcode.com/problems/sort-list/)
本題會使用到資料結構linked list。
題目給定一個linked list的數列，其中的數字並未排序，請將數列排序後，回傳排序好數列的linked list。
:::success
提示：初學者可採用將linked list轉為array後來排序。高手建議可嘗試用merge sort，以divide and conquer的概念來作。
:::

## 第5題: 將排序好的數列轉為二元搜尋樹
[Convert Sorted Array to Binary Search Tree - LeetCode](https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/submissions/)
本題會使用到資料結構Tree中的二元搜尋樹。
已知一個排序好的數列，請將每個數字為一個點，建構一個二元搜尋樹。
例如：數列為[-10,-3,0,5,9]時，可轉為以下的二元搜尋樹(兩種皆可)
:::success
提示：取數列的中間值為root，並將數列分為左右兩個數列，用左數列建立root的左子樹，用右數列建立root的右子樹。
:::
相關題(自由作答)：[Convert Sorted List to Binary Search Tree - LeetCode](https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/submissions/) 與上題類似，僅把輸入改為linked list

## 第6題：心得
- 請寫下對於期中考的心得，以及本週影片教學的疑問以及程式作業的適應情況。

## 挑戰題(自由作答): 美麗數列
[Beautiful Array - LeetCode](https://leetcode.com/problems/beautiful-array/)
將n個數字(從1到n)排列，使得任意兩數之間，不存在該兩數和的一半的數字。這種排列稱為美麗數列(Beautiful Array)。
舉例來說, n=3時，1,2,3就不合規定，因為(1+3)/2=2，而2就在1,3之間。1,3,2就合乎規定。
n=4時，1,2,3,4和1,2,4,3以及3,2,4,1都不合規定因為2都在1,3之間。而1,3,2,4就合乎規定。
題目會給定n，請找出一組合乎規定的排列。