# 演算法作業09

## 第1題: 最短路徑

### 請使用Branch-and-Bound找出下圖中，S到T的最短路徑。請畫出Branch-and-Bound圖，並標示各點的cost，以及被bound住的地方。(可參考ppt20頁)


:::success
#### hill climbing

#### 如果Bound會更新的話

#### 如果Bound不會更新的話

GIF太大傳不上來QQ
:::

## 第2題: Personnel Assignment Problem

- 已知5個工作($j_1,…,j_5$)，其先後關係為：$j_1\to j_3 , j_3 \to j_4 , j_2 \to j_5$，分配給5個人員($p_1,…,p_5$)
- 每人分配一個工作，且當$j_a < j_b$ ，須要 $p_a < p_b$。
- 請使用Branch-and-Bound找出最少費用的人員工作分配。

:::info
#### 提煉cost matrix

##### 原始矩陣

$\begin{bmatrix}
17 & 13 & 4 & 23 & 12\\
32 & 30 & 45 & 19 & 31\\
7 & 11 & 12 & 3 & 15 \\
10 & 17 & 13 & 9 & 11\\
8 & 19 & 9 & 6 & 7
\end{bmatrix}$

##### 橫排提煉後

$\begin{bmatrix}
13 & 9 & 0 & 19 & 8\\
13 & 11 & 26 & 0 & 12\\
4 & 8 & 9 & 0 & 12 \\
1 & 8 & 4 & 0 & 2\\
2 & 13 & 3 & 0 & 1
\end{bmatrix}$

4+19+3+9+6 = 41

##### 直排提煉後

$\begin{bmatrix}
12 & 1 & 0 & 19 & 7\\
12 & 3 & 26 & 0 & 11\\
3 & 0 & 9 & 0 & 11 \\
0 & 0 & 4 & 0 & 1\\
1 & 5 & 3 & 0 & 0
\end{bmatrix}$

41 + (1+8+1) = 51

基本成本就是51
:::

:::info
稍微畫個拓樸排序 等等可以對照
:::

:::success
### B&B結果

:::

## 第3題: Traveling Salesperson Optimization Problem

- 在ppt34頁中，該例首先以4-6將所有feasible solution分為兩集合。
- 現在，將原例的4-6改以6-7來作區分，接著再以3-5作區分，如下圖所示：


- 請計算出圖中每個紅框的lower bound，並列出reduced matrix。

:::info

### 原始reduced matrix


## lower bound = 96

:::

:::success


#### lower bound = 96 + 0 = 96


把7-6改成無限、把第7欄刪掉
因為第6列有一個0了，所以不用縮減

:::

:::success

#### lower bound = 96 + 0 + 5 = 101

:::

:::success
#### lower bound = 96 + 0 = 96

把5-3改成無限、把第5欄刪掉
因為第5列有一個0了，所以不用縮減

:::

:::success
#### lower bound = 96 + 1 + 17 = 114

:::

:::success
每個的lower bound
:::

## 第4題: 左右反轉二元樹

### 解題思路

左右子樹的結點都翻一次
整棵樹就翻過來了
寫個遞迴給他左右翻轉
蠻簡單的

### 程式碼

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(root == NULL)
        {
            return NULL;
        }
        TreeNode* L = new TreeNode();
        L = root->left;
        TreeNode* R = new TreeNode();
        R = root->right;
        if(L!=NULL)
        {
            invertTree(L);
        }
        if(R!=NULL)
        {
            invertTree(R);
        }
        root->left=R;
        root->right=L;
        return root;
    }
};

### 測試輸出輸入的畫面截圖


### 花費時間

9分鐘

### 完成程度

完全自己解出

## 第5題:

### 解題思路

因為二元搜尋樹的中序就是從小排到大
中序跑一次就好，全域變數紀錄跑到第幾個這樣

### 程式碼

class Solution {
public:
    int num = 0,ans = 0;
    int kthSmallest(TreeNode* root, int k) {
        num = 0;
        ans = 0;
        f(root,k);
        return ans;
    }
    void f(TreeNode* root, int k) {
        if(root == NULL)
        {
            return;
        }
        f(root->left,k);
        num++;
        if(num == k)
        {
            ans = root->val;
            return;
        }
        if(num > k)
        {
            return;
        }
        f(root->right,k);
    }
};

### 測試輸出輸入的畫面截圖


### 花費時間

5分鐘

### 完成程度

完全自己解出

## 第6題:

### 解題思路

紀錄目前遇到的最深的節點
如果遇到更深的，就把`LD`更新、把sum歸零，並把點的數值加到`sum`
如果遇到跟最深的一樣深，就把點的數值加到`sum`

### 程式碼

class Solution {
public:
    int LD = -1;
    int sum = 0;
    int deepestLeavesSum(TreeNode* root) {
        LD = -1;
        sum = 0;
        f(root , 0);
        return sum;
    }
    void f(TreeNode* root,int d)
    {
        if(root == NULL)
        {
            return;
        }
        if(d > LD)
        {
            sum = root->val;
            LD = d;
        }
        else if( d == LD )
        {
            sum += root->val;
        }
        f(root->left,d+1);
        f(root->right,d+1);
    }
};

### 測試輸出輸入的畫面截圖


### 花費時間

10分鐘

### 完成程度

完全自己解出

## 心得:

已填