演算法作業 HW7

本週程式題的難度漸漸提升。
這次主題是Ch4 Divide and Conquer。這類程式常用遞迴的方式來寫。
另外，有使用到資料結構裏的linked list與tree。若不清楚，請復習一下。

觀念題

第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

第4題: 將linked list的數列排序

Sort List - LeetCode
本題會使用到資料結構linked list。
題目給定一個linked list的數列，其中的數字並未排序，請將數列排序後，回傳排序好數列的linked list。

提示：初學者可採用將linked list轉為array後來排序。高手建議可嘗試用merge sort，以divide and conquer的概念來作。

第5題: 將排序好的數列轉為二元搜尋樹

Convert Sorted Array to Binary Search Tree - LeetCode
本題會使用到資料結構Tree中的二元搜尋樹。
已知一個排序好的數列，請將每個數字為一個點，建構一個二元搜尋樹。
例如：數列為[-10,-3,0,5,9]時，可轉為以下的二元搜尋樹(兩種皆可)

提示：取數列的中間值為root，並將數列分為左右兩個數列，用左數列建立root的左子樹，用右數列建立root的右子樹。

相關題(自由作答)：Convert Sorted List to Binary Search Tree - LeetCode 與上題類似，僅把輸入改為linked list

第6題：心得

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

挑戰題(自由作答): 美麗數列

Beautiful Array - LeetCode
將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，請找出一組合乎規定的排列。