演算法作業10

第1題: 01背包問題

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

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

已經按照

$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

只需要從前面開始取就好

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$

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)-(\lfloor 10+5/2\rfloor )=-19$
upper bound

$=-(7)-(10)=-17$

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

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

$=-(10+4)=-14$

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$

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$

結果

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

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

過程

結果

第3題: Channel Routing Problem

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

更新後的水平&垂直限制

過程

結果

第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分鐘

完成程度

完全自己解出

心得:

已填