# 演算法 HW1

## :book: 觀念題

### 第一題 本週影片中提到的NP-complete問題有哪些？

* **NP-complete問題** : 此問題目前不存在一個有效率的解法。
* **有效率** : 在解決一個問題時，隨著問題增加，時間增長幅度不會太快。
* 常見的沒有效率的方法 : **暴力法**、**窮舉法**。
* 影片中提到的NP-complete問題 :
1. **0/1 Knapsack problem**
將一群物品儘量塞進背包裡面，使背包裡面的物品總價值最高。背包有重量限制，如果物品太重。
* 舉例(如下圖):
假設背包能承受最大重量為14，則 P1,P2,P3,P5即為本題最佳解。
* 方法:
先找出每項物品單位價值，再由大到小裝入背包。(但背包可能會有多餘的空間)--不一定為最佳解。

2. **Traveling salesperson problem**
給定一系列城市和每對城市之間的距離，求解訪問每一座城市一次並回到起始城市的最短迴路。
* 舉例(如圖):
* 方法:
1. 每次找距離該點最近的點。--可能導致回程距離太大。
2. 列出所有點的排序，並計算最短距離。
3. **Partition problem**
將已知的集合分成兩個子集，這兩個子集的元素分別總和是相等的，且兩子集的元素不得已重複，所有元素皆須用到。
* 舉例:
S={1,7,10,4,6,8,3,13},其解為
S1={1,10,4,8,3}, S2={7,6,13}
* 方法:
先算出所有元素總和，再將結果除以2，再一一分群(列出所有可能)，直到分成兩群分別和等於此結果。

4. **Art gallery problem**
給定一個藝廊的平面圖，我們要安排警衛的人數與位置使得警衛的人數要最少，但是藝廊裡的每一個角落都至少要有一個警衛能監視到。
* 舉例(如圖):
* 方法:
列舉法也無法解題，需使用特別的解題方式，如直接觀察。

### 第二題 請上網找一個老師沒說過的NP-complete問題，並舉個例子說明該問題的輸入與輸出。
**分團問題(clique problem)**
* 什麼是團(clique) ?
就是 一個Graph，裡面 有一塊 是complete graph。
* 問一個圖中是否有大小是k以上的團?
* 任意挑出k個點，我們可以簡單的判斷出這k個點是不是一個團。
* 舉例(如下圖):
若k是3，而圖中1,2,5即為一個complete graph，我們就將其稱之為團(clique)。


* **方法**
1. 使用暴力法在V個點的圖中列舉k個點得子集合，並判斷是否為一個團。
2. 先找出所有一個點的團，在進行合併。

## :desktop_computer: 程式題 (使用語言 : C++)

### 示範題 改C++

* leetcode 704
* 時間:5分鐘
* 自己完成的程度：完全靠自己
* 程式碼:

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left=0,right=nums.size()-1,mid;
        int answer=-1;
        while(left<=right)
        {
            mid=(left+right)/2;
            if(target==nums[mid])
            {
                answer=mid;
                break;
            }
            else if(target<nums[mid])
            {
                right=mid-1;
            }
            else
            {
                left=mid+1;
            }
        }
        return answer;
    }
};

* 通過截圖 :


### 第三題 二元搜尋應用：當數字可以重覆

* leetcode 704延伸
* 時間:10分鐘
* 自己完成的程度：完全靠自己
* 程式碼:

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left=0,right=nums.size()-1,mid;
        int answer=-1;
        while(left<=right)
        {
            mid=(left+right)/2;
            if(target==nums[mid])
            {
                answer=mid;
                right=mid-1;
            }
            else if(target<nums[mid])
            {
                right=mid-1;
            }
            else
            {
                left=mid+1;
            }
        }
        return answer;
    }
};

* 通過截圖(為leetcode 704通過截圖)



### 第四題 二元搜尋應用：找數字該插入的位置

* leetcode 35
* 時間:1小時
* 自己完成的程度：參考網路資料
* 程式碼:

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left=0;
        int right=nums.size()-1;
        int mid;
        while(left<=right)
        {
            mid=(left+right)/2;
            if(target==nums[mid]) 
                return mid;
            else if(target<nums[mid]) 
                right=mid-1;
            else if(target>nums[mid]) 
                left=mid+1;
        }

        return left;
    }
};

* 通過截圖


### 第五題 二元搜尋應用：找到最早出問題的版本

* leetcode 278
* 時間:1小時
* 自己完成的程度：靠自己
* 程式碼:

class Solution {
public:
    int firstBadVersion(int n) {
        int left=1;
        int right=n;
        int mid;
        int ans=-1;
        while(left<=right)
        {
            mid=left+(right-left)/2;
            if(isBadVersion(mid))
            {
                ans=mid;
                right=mid-1;
            }
            else if(!isBadVersion(mid))
            {
                left=mid+1;
            }
        }
        return ans;
    }
};

* 通過截圖


### 第六題 二元搜尋應用：開根號後的整數部分

* leetcode 69
* 時間:2小時
* 自己完成的程度：自己coding完有錯，找不到bug，請同學幫忙並自己修正
* 程式碼:

class Solution {
public:
    int mySqrt(int x) {
        int mid=0;
        int num=-1;
        int ans=0;
        double middle=0.0;
        int left=0;
        int right=x;
        if(x<=1)
            return x;
        while(true)
        {
            middle=(left+right)/2;
            mid=middle;
            if(middle*middle==x || mid==num)
            {
                ans=mid;
                break;
            }
            else if(middle*middle<x)
            {
                left=middle+1;
                num=middle;
            }
            else if(middle*middle>x)
            {
                right=middle-1;
                num=middle;
            }
        }
        return ans;
    }
};

* 通過截圖


## :pushpin:心得

### 第七題 本週心得

影片中老師講解得很仔細，之前就有聽過其中的NP-complete這個詞，但並不是很理解在做甚麼。看完影片後感覺有更了解了，也發現原來生活中很多看似簡單的問題，其實都屬於NP-complete。
作業由淺入深，從程式第一題開始理解二元搜尋怎麼用，到後面開根號的逼近也能用二元搜尋法解題，雖然後面題目寫得比較久，也思考得比較久，但覺得還行。

###### tags: `演算法`