# 演算法作業一

## 1. 本週影片中提到的NP-complete問題有哪些？
1. 0/1 Knapsack Problem (01背包問題)
- 輸入：
1. 給你一個物品的集合，此物品的資訊有兩個：價值、重量
2. 給你背包的最大重量
- 輸出：
1. 請找出該背包可裝那些屋品以達到最大價值

2. Traveling Salesperson Problem (旅行推銷員問題)
- 輸入：
1. 給你一個圖，邊上紀錄著長度
- 輸出：
1. 請找出一個路徑可以拜訪所有頂點，且長度最短
3. Partition Problem (分組問題)
- 輸入：
1. 給你一個集合
- 輸出：
1. 找出兩個子集合：$A,B$，使$\Sigma A=\Sigma B \space such \space that \space A\land B=\emptyset$

4. Art Gallery Problem (畫廊問題)
- 輸入：
1. 給你一個地圖
- 輸出：
1. 用最少的守衛使該地圖的每個角落都可以被照料到

## 2. 請上網找一個老師沒說過的NP-complete問題，並舉個例子說明該問題的輸入與輸出。

1. Minesweeper(踩地雷)
- 輸入：給定一個n*n的方格並有若干個地雷，包含一些已經打開的數字和可能會有的一些已經標記的地雷
- 輸出：找出所有沒有地雷的方格

## 二分搜尋法
:::info
###### 防止mid溢位的對策
- python的int是無上限的，所以我們可以用

	mid = (left+right) // 2

**但是**，C++的整數存在範圍限制，所以可以用

	int mid = left + (right-left) / 2;

- 證明如下
As we know, $left<=right<=INT\_MAX$
$left+(right-left) = right <= INT\_MAX$
and, $left+(right-left)/2 <=left+(right-left) = right <= INT\_MAX$
Q.E.D.
:::
### implement by recusive

int binarySerch(vector<int>& arr, int target,int left,int right){
	int mid = left + (right - left) / 2;
	if (left > right)
		return -1;
	
	if (arr[mid]==target)
		return mid;
	else if (arr[mid]>target)
		return binarySerch(arr, target,left,mid-1);
	else
		return binarySerch(arr, target,mid+1,right);
}

### implement by iterative

int binarySerch(vector<int>& arr,int target){
	int left  = 0;
	int right = arr.size()-1;
	
	while (left<=right){
		int mid = left + (right - left) / 2;
		
		if (arr[mid] == target){
			return mid;
		}
		else if (arr[mid]>target){
			right = mid - 1;
		}
		else{
			left = mid + 1;
		}
	}
	return -1;
}

## 3. 二元搜尋應用：當數字可以重覆
- 程式碼

#include<bits/stdc++.h>
using namespace std;

int lowerBound(vector<int>& arr,int target){
	int left  = 0;
	int right = arr.size()-1;

	int ans = -1;
	while (left<=right){
		// prevent overflow
		int mid = left + (right-left)/2;
		if (arr[mid] < target){
			left = mid+1;
		}
		else{
			right = mid-1;
			ans = mid;
		}
	}
	if (ans == -1){
		return ans;
	}
	return arr[ans]==target?ans:-1;
}

int main(){
	vector<int> arr;
	int n;
	cout<<"How many Element?\n";
	cin>>n;
	while (n--){
		int element;
		cin>>element;
		arr.push_back(element);
	}
	int target;
	cin>>target;
	cout<<lowerBound(arr,target)<<endl;
	return 0;
}

- 執行結果
- Program Language：C++
- 花費時間：15分鐘
- 完成程度：靠自己
- 思路：
1. 先對vector進行二分搜
2. 有個問題：因為有重複值所以要找最小index的地方，因此可以使用lowerBound的概念找出
3. 這時我們可以使用ans存取，如果`target == arr[mid]`我就用ans存取，並向左邊查詢還有沒有該值

## 4. 二元搜尋應用：找數字該插入的位置
[leetcode 35](https://leetcode.com/problems/search-insert-position/)
- 程式碼：

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        return upperBound(nums,target);
    }
private:
    int upperBound(vector<int>& arr,int target){
        int left  = 0;
        int right = arr.size()-1;

        int ans = 0;
        while (left<=right){
            int mid = left + (right - left)/2;

            if (arr[mid] == target){
                return mid;
            }
            else if(arr[mid]>target){
                right = mid - 1;
            }
            else{
                left = mid + 1;
                ans = left;
            }
        } 
        return ans;
    }
};

- 執行結果
- Program Language：C++
- 花費時間：5分鐘
- 完成程度：靠自己
- 思路：
1. 跟剛剛那題目很像，只是改成找upperBound而已

## 5. 二元搜尋應用：找到最早出問題的版本
[leetcode 278](https://leetcode.com/problems/first-bad-version/)
- 程式碼

class Solution {
public:
    int firstBadVersion(int n) {
        int left  = 1;
        int right = n;

        int ans = -1;
        while (left<=right){
            int mid = left + (right - left)/2;

            if (isBadVersion(mid)){
                ans   = mid;
                right = mid - 1;
            }
            else{
                left = mid + 1;
            }
        }
        return ans;
    }
};

- 執行結果
- Program Language：C++
- 花費時間：1分鐘
- 完成程度：靠自己
- 思路：
1. 可以將版本看成一個序列
:::success
###### **以測試資料1為例子，我們可以將版本看成**
version = [0,0,0,1,1]

>0：true, 1: false
:::
2. 如此一來問題簡化成尋找1，且index最少，和第三題一模模一樣樣

## 6. 二元搜尋應用：開根號後的整數部分
[leetcode 69](https://leetcode.com/problems/sqrtx/)
- 程式碼

class Solution {
public:
    int mySqrt(int x) {
        int left  = 1;
        int right = x;

        if (x==1 || x == 0) return x; // Sepcial case

        int ans = 1;
        while (left <= right){
            int mid = left + (right-left)/2;

            if (mid > x/mid){ //In order to prevent mid * mid overflow, I use mid > x/mid
                right = mid - 1; 
            }
            else {
                left = mid + 1;
                ans = mid;
            }
        }
        return ans;
    }
};

- 執行結果
- Program Language：C++
- 花費時間：5分鐘
- 完成程度：大部分靠自己，但有看解答(等等說明)
- 思路：
~~我本來想用牛頓法後來想說算了好累哈哈~~
1. 一樣我們可以把他看成一個序列進行搜尋
:::success
###### **我們以case 2舉例(case 1太理想了哈)**
ans = [$1$,$2^2$,$3^2$,$4^2$,$5^2$,$6^2$,$7^2$,$8^2$]
:::
2. 則我們要找的答案就是target在ans的lowerBound
3. 好我查網路的原因來了，我的程式碼就這樣寫

		if (mid*mid > x){ 
            right = mid - 1; 
        }
        else {
            left = mid + 1;
            ans = mid;
        }

阿結果就overflow了討厭，所以我去查答案，有一個大師把mid除過去，以防止overflow，讚

		if (mid > x/mid){ 
            right = mid - 1; 
        }
        else {
            left = mid + 1;
            ans = mid;
        }

## 7. 本週心得
今天寫了好多二分搜，我以為我二分搜超級熟，結果沒有:<，我比較印象深刻的還是第三題，我記得我有卡了一下，但後來有想到他其實跟lowerBound的概念有點像，結果扣就剛好被我搞出來了好港動。

我其實針對這周比較有問題的是，我要怎麼去評斷該問題是NP完全，我知道P問題跟NP問題差別是，P問題是該問題可再多項式時間答出來，NP問題是我可以在多項式時間驗證出來，但我不太懂NP完全要怎麼判斷，希望老師可以說明一下。