---
# System prepended metadata

title: 自主學習講義

---

# <center>輾轉相除法
**輾轉相除法是一種尋找兩數最大公因數的方法，也叫做歐幾里得演算法。以下是它的基本步驟：**

**給定兩個"正"整數a和b，並讓a >= b。
將a除以b取得商數和餘數 (a = bq + r)。
如果餘數r等於0，那麼b就是a和b的最大公因數。
如果餘數r不等於0，那麼讓a = b，b = r，並回到第二步繼續運算，直到找到最大公因數。**
    
## <center>證明
**假設d1 = (a , b)，d2 = (b , r)，求證d1 = d2。**
**因為d1是a和b的最大公因數，因此 d1|b，d1|a。("|"為整除的意思)**
**因此存在整数1和q滿足a = bq + r，得 r=a−bq=a×1−b×q 且 r為d1之倍數**
**也就是d1|(b,r)。所以d1|d2。**
    
**因為d2是b和r的最大公因數，所以 d2|b，d2|r。
因此同樣存在整數1和q。得 a=bq+r=b×q+r×1 所以d2|a(q為整數，且b跟a為d2之倍數)，
也就是d2|(a,b)，所以d2|d1。
而 d1|d2 且 d2|d1 ，在d1和d2都大於等於1(最大公因數)，因此d1 = d2，
即(a , b) = (b , r) 得證。**

## **題目練習**
**https://zerojudge.tw/ShowProblem?problemid=a024**
## **參考程式碼**
```cpp=
#include<bits/stdc++.h>
#define endl '\n'
#define IO cin.tie(0) -> sync_with_stdio(0)
using namespace std;

int gcd(int a , int b){
	int times = a/b;
	int r = a - b * times;
	if(r == 0) return b;
	else return gcd(b , r);
}

int main(){
	int a , b;
	while(cin >> a >> b){
		cout << gcd(a , b) << endl;
	}
}
```
    
# <CENTER>LCS最長共同子序列
 **最長共同子序列定義如下：如有兩序列 S1 、 S2 ，兩序列各自可分離出若干個子序列。若 S1 存在一個子序列 S1 並且 S2 存在一個子序列 S2 完全相等於 S1 ，則稱該子序列為兩序列 S1 、 S2 的共同子序列。**
**子序列定義如下：在不違反原序列的順序之下，挑出任意個元素重新形成的有序元素列。**
**題目:**
**https://dandanjudge.fdhs.tyc.edu.tw/ShowProblem?problemid=a310**
```cpp=
    #include<bits/stdc++.h>
#define endl '\n'
#define IO cin.tie(0) -> sync_with_stdio(0)
using namespace std;
typedef long long ll;

signed main(){
    IO;
    string s1 , s2;
    while(cin >> s1 >> s2){
        s1 = "*" + s1 ; s2 = "*" + s2;
        int SCROLL[2][s2.size()];
        memset(SCROLL , 0 , sizeof(SCROLL));
        for(int i = 1 ; i < s1.size() ; i++){
            for(int j = 1 ; j < s2.size() ; j++){
                if (s1[i] == s2[j])
                    SCROLL[i % 2][j] = SCROLL[(i - 1) % 2][j - 1] + 1;
                else
                    SCROLL[i % 2][j] = max(SCROLL[(i - 1) % 2][j], SCROLL[i % 2][j - 1]);
            }
        }
        cout << SCROLL[(s1.size() - 1) % 2][s2.size()-1] << endl;
    }
    return 0;
}

```
# <center> 背包問題
**一種求最佳解的方式，像是有一個背包(容量有限)，問裝哪些東西能獲得的目標值最多?**
## 01背包
每項物品都只有一個

背包容量為`M`,有`N`個物品。
$v[i] \implies 第i個物品的價值$
$w[i] \implies 第i個物品的重量$
**https://dandanjudge.fdhs.tyc.edu.tw/ShowProblem?problemid=a279**
```cpp=
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
int main(){
	int n , c;
	while(cin >> n >> c){ // n 個數 ; c 容量 
		int dp[c+1];
		int a[n] , b[n];//a價值 b體積 
		memset( dp, 0, sizeof(dp));
		
		// int x[]
		//memset(x, 0, sizeof(x))
		memset(a,0,sizeof(a));
		memset(b,0,sizeof(b));
		for(int i = 0 ; i < n ; i++){
			cin >> a[i] >> b[i];
		}
		for(int i = 0 ; i < n ; i++){
			for(int j = c ; j >= b[i] ; j--){
				dp[j] = max(dp[j] , a[i] + dp[j-b[i]]);
			}
		}
		cout << dp[c] << endl;
	}
}
```
## 有限背包
    #### 一開始的想法
把每一個物品都做一次`O/1背包`。

```cpp=
vector<int> v(N), w(N), k(N);
vector<int> dp(M + 1, 0);
for(int i = 0; i < N;i ++) 
    for(int t = 0; t < k[i]; t++) 
        for(int j = M; j >= w[i]; j--) 
            dp[j] = max(dp[j], v[i] +　dp[j - w[i]])；
```

時間複雜度$O(kMN)$
空間複雜度$O(M)$
#### 嘗試優化
把物品的數量拆成二的倍數。
```cpp= 
vector<int> v(N), w(N), k(N);
for(int i = 0; i < N; i++) {
    int rest = k[i];
    int weight, val;
    
    for(int t = 1; t <= rest; t <<= 1) { //t *= 2
        rest -= t;        
        weight = t * w[i], val = t * val[i];
        
        for(int j = M;j >= weight; j--)
            dp[j] = max(dp[j], val + dp[j - weight]);
    }
    
    
    weight = t * w[i], val = t * v[i];
    
    for(int j = M; j >=; j++) {
        dp[j] = max(dp[j], val + dp[j - weight]);
    }
}
```

時間複雜度$O(NM\log k)$ 
空間複雜度$O(M)$

https://dandanjudge.fdhs.tyc.edu.tw/ShowProblem?problemid=a330
    
## 無限背包
從前往後`DP`, 即可。
https://dandanjudge.fdhs.tyc.edu.tw/ShowProblem?problemid=a331
```cpp=
#include<bits/stdc++.h>
#define endl '\n'
#define mms memset
#define ll long long
using namespace std;
int main(){
	ll n , c;//n個 ; c容量 
	while(cin >> n >> c){
		ll av[n];ll bw[n];ll dp[c+1];
		mms(av , 0 , sizeof(av));
		mms(bw , 0 , sizeof(bw));
		mms(dp , 0 , sizeof(dp));
		for(int i = 0 ; i < n ; i++){
			cin >> av[i] >> bw[i];
		}
		for(int i = 0 ; i < n ; i++){
			for(int j = bw[i] ; j <= c ; j++){
				dp[j] = max( dp[j] , av[i] + dp[j-bw[i]]);
			}
		}
		cout << dp[c] << endl;
	}
}
```