# <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;
}
}
```
Sign in with Wallet
Connect another wallet