# 演算法作業10

## 第1題: 01背包問題

### 已知有六個物品，其價值和重量如下，背包重量限制為34。


- 仿照課本以tree search來解。
- 請將下圖中的框框中，填入其upper bound與lower bound


:::info

已經按照$P_i/W_i$大小排了

| $i$ | 1 | 2 | 3 | 4 | 5 | 6 |
| --------- | ---- | ----- | --- | --- | --- | --- |
| $P_i$ | 7 | 10 | 4 | 4 | 4 | 2 |
| $W_i$ | 10 | 19 | 8 | 10 | 12 | 8 |
| $P_i/W_i$ | 7/10 | 10/19 | 1/2 | 2/5 | 1/3 | 1/4 |

只需要從前面開始取就好

:::

:::success

#### 0

| $i$ | 1 | 2 | 3 | 4 | 5 | 6 |
| --------- | ---- | ----- | --- | --- | --- | --- |
| $P_i$ | 7 | 10 | 4 | 4 | 4 | 2 |
| $W_i$ | 10 | 19 | 8 | 10 | 12 | 8 |
| $P_i/W_i$ | 7/10 | 10/19 | 1/2 | 2/5 | 1/3 | 1/4 |

lower bound $=-(\lfloor 7 + 10 + 5/2\rfloor)=-19$
upper bound $=-(7 + 10)=-17$

:::

:::success

#### 1


| $i$ | 1 | 2 | 3 | 4 | 5 | 6 |
| --------- | ---- | ----- | --- | --- | --- | --- |
| $P_i$ | 7 | 10 | 4 | 4 | 4 | 2 |
| $W_i$ | 10 | 19 | 8 | 10 | 12 | 8 |
| $P_i/W_i$ | 7/10 | 10/19 | 1/2 | 2/5 | 1/3 | 1/4 |

lower bound $= -(7) -(\lfloor10 + 5/2\rfloor)=-19$
upper bound $=-(7) -(10)=-17$

:::

:::success

#### 2


| $i$ | ~~1~~ | 2 | 3 | 4 | 5 | 6 |
| --------- | ---- | ----- | --- | --- | --- | --- |
| $P_i$ | ~~7~~ | 10 | 4 | 4 | 4 | 2 |
| $W_i$ | ~~10~~ | 19 | 8 | 10 | 12 | 8 |
| $P_i/W_i$ | ~~7/10~~ | 10/19 | 1/2 | 2/5 | 1/3 | 1/4 |

lower bound $= -(\lfloor10 + 4 + 14/5\rfloor)=-16$
upper bound $= -(10+4)=-14$

:::

:::success

#### 3


| $i$ | 1 | 2 | 3 | 4 | 5 | 6 |
| --------- | ---- | ----- | --- | --- | --- | --- |
| $P_i$ | 7 | 10 | 4 | 4 | 4 | 2 |
| $W_i$ | 10 | 19 | 8 | 10 | 12 | 8 |
| $P_i/W_i$ | 7/10 | 10/19 | 1/2 | 2/5 | 1/3 | 1/4 |

lower bound $= -(7 + 10) -(\lfloor 5/2\rfloor)=-19$
upper bound $=-(7+10)=-17$

:::

:::success

#### 4


| $i$ | 1 | ~~2~~ | 3 | 4 | 5 | 6 |
| --------- | ---- | ----- | --- | --- | --- | --- |
| $P_i$ | 7 | ~~10~~ | 4 | 4 | 4 | 2 |
| $W_i$ | 10 | ~~19~~ | 8 | 10 | 12 | 8 |
| $P_i/W_i$ | 7/10 | ~~10/19~~ | 1/2 | 2/5 | 1/3 | 1/4 |

lower bound $= -(7 ) -(\lfloor 4 + 4 + 6/3\rfloor)=-17$
upper bound $=-(7) -(4+4)=-15$

:::

:::success
### 結果
:::

## 第2題: A* 解multi-stage shortest path problem

- 請使用A* 找出S到T的最短路徑。請畫出樹狀圖，並標示各點的cost，並註明哪裏分枝不用再繼續尋找了


:::success
#### 過程


##### 結果


:::

## 第3題: Channel Routing Problem

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


:::info
#### 更新後的水平&垂直限制

:::

:::success
#### 過程

#### 結果

:::

## 第4題: 合併二元樹

### 解題思路

DFS跑一次，主要是NULL的處理比較麻煩
其他都還好

### 程式碼

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if(root1 == NULL && root2 == NULL)
        {
            return NULL;
        }
        TreeNode* ans = new TreeNode();
        if(root1 != NULL )
        {
            ans->val+=root1->val;
        }
        if(root2 != NULL )
        {
            ans->val+=root2->val;
        }
        if(root1 == NULL)
        {
            ans->left = mergeTrees(NULL,root2->left);
            ans-> right = mergeTrees(NULL,root2->right);            
        }
        else if(root2 == NULL)
        {
            ans->left = mergeTrees(root1->left,NULL);
            ans-> right = mergeTrees(root1->right,NULL);            
        }
        else
        {
            ans->left = mergeTrees(root1->left,root2->left);
            ans-> right = mergeTrees(root1->right,root2->right);            
        }
        return ans;
    }
};

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


### 花費時間

10分鐘

### 完成程度

完全自己解出

## 第5題: 最深葉子的最低共同祖先

### 解題思路

我用後序的想法去寫，然後我寫一個函數專門計算深度&答案
然後因為後序，所以越上面的點會越晚被更新，
最後被更新的就會是答案，yeah

### 程式碼

class Solution {
public:
    TreeNode* ans;
    int TD=-1;
    int f(TreeNode* root , int d)
    {
        if(root == NULL)
        {
            return d;
        }
        int l = f(root->left, d+1);
        int r = f(root->right, d+1);
        TD = max(TD,l);
        TD = max(TD,r);
        if(r > l)
        {
            return r;
        }
        if(l == r && l == TD)
        {
            ans = root;
        }
        return l; 
    }

    TreeNode* lcaDeepestLeaves(TreeNode* root) {
        ans = new TreeNode();
        f(root,0);
        return ans;
    }

};

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


### 花費時間

30(想錯的時間) + 15分鐘

### 完成程度

完全自己解出

## 第6題:

### 解題思路

寫個遞迴，判斷是否下面的子樹都是0或空，如果是就把點改成`NULL`並回傳0
反之就回傳1，以便上面的點去保留

return l||r||root->val;

這串就是在回傳左右子樹的檢查結果跟自身的檢查結果這樣

### 程式碼

class Solution {
public:

    bool f(TreeNode* root)
    {
        if(root == NULL)
        {
            return 0;
        }
        int l = f(root->left);
        int r = f(root->right);
        if(!l)
        {
            root->left = NULL;
        }
        if(!r)
        {
            root->right = NULL;
        }
        return l||r||root->val;
    }

    TreeNode* pruneTree(TreeNode* root) {
        f(root);
        if(!root->val&&root->left==NULL&&root->right==NULL)
        {
            return NULL;
        }
        return root;
    }
};

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


### 花費時間

15分鐘

### 完成程度

完全自己解出

## 心得:

已填