DSA 第十週講義

練習: Add All

根據題目要求，我們要相加一個數列。而每兩個數字的相加成本為其相加後的總和。例如:
3+5 = 8 –> cost: 8
我們可以觀察一下範例測資，尋找輸出最小成本的規則

解答:
因為相加後的數視為一個新的數，所以n個數固定要加n-1次，導致每次相加的兩個數越小越好(目前最小的兩個數相加)

細節:

1. 注意輸入大小，或相加過程中是否溢位
2. 時間: 由於此題輸入量5000 –> 如何有效率地尋找最小值，並在相加後排序

priority_queue

在寫競程時，排序有助於我們方便地對資料套用一些演算法。但同時也要注意排序所花的時間。
在這裡，每相加一次就要做排序 –> 若今天數列5000個 –> 做5000-2次排序。
此時，可以考慮STL以幫你寫好的容器且會排序，如:set、mutliset還有這裡的priority_queue(以下簡寫pq)

由於pq不是greedy的重點，這裡不會講太多，可以參考下面網址
連結1
連結2
連結3

• pq.push(x): 將x加進pq
• pq.pop(): 將最大(小)的數字取出
• pq.top(): 檢視最大(小)的數字
• pq.size(): 回傳pq長度
• pq.empty(): 回傳有無數字

宣告
 
priority_queue<int> pq1 // 由大排到小
priority_queue<int, vector<int>, greater<int>> pq2 // 由小排到大

程式碼:

#include <bits/stdc++.h>
using namespace std;
 
 
typedef long long ll;
int const MaxN = 5000;
int a[MaxN], N;
 
int main() {
	ios::sync_with_stdio(0); //  資料有點多，加速讀取
	cin.tie(0);
	
	while (1){
		ll x, cost = 0; // cost可能溢位
		priority_queue<ll, vector<int> , greater<int> > pq;
		
		cin >> N;
		if (N <= 0)break;
		for (int i=0;i<N;i++){
			cin >> x;
			pq.push(x);
		}
		
		while (pq.size()>1){
			// 取最小的兩個數字
			ll x1, x2;
			x1 = pq.top();
			pq.pop();
			x2 = pq.top();
			pq.pop();
			
			x = x1+x2;
			cost+=x;
			pq.push(x);// 加完記得塞回去
			
		}
		cout << cost << endl;
	}
	
	
	return 0;
}

什麼時候適合用DP?

1. 最佳子結構性質：子問題的解可以推到原本的問題的解。
2. 重疊子問題：常常需要處理相同的子問題

• 不符合第一點的話沒辦法用DP
• 符合第二點的時候，記憶化儲存就能有效減少執行次數，以空間換取時間

DP VS 分治

• DP: DP的子問題是由原問題遞推出來的，所以常常需要處理相同的子問題

• 分治: 分治的子問題是由大問題切割出來的，雖不大重複，但會有跨區問題

DP要點

dp 由四大要素組成

1. 尋找遞迴式(recurrence)
2. 定義子問題(state space)
3. 狀態轉移(state transition)
4. 找到原問題的答案

1. 尋找遞迴式(recurrence)

找出這個問題的規律，像解數學一樣寫出遞迴關係式

ex.費式數列

• 設費式數列第n項為f(n)
  f(n){
  n=1 , f(1)=1
  n=2 , f(2)=1
  n>2 , f(n)=f(n-2)+f(n-1)}

2. 定義子問題(state space)

(1)在分治法中，我們需要決定切割問題的方法；在dp中，我們則需要知道會出現的子問題有那些，來決定要計算的範圍

(2)開一個陣列當答案的存放區，依據要計算的範圍決定陣列的長度、答案放的位置

ex.尋找費式數列第\(n\)項
(1)需要計算的子問題:第一項的值、第二項的值、…、第\(n\)項的值
(2)開個長度為\(n+1\)的陣列\(f\)，決定把第i項的值放在 \(f[i]\)

ps.你也可以直接將陣列長度固定為\(max_n+1\)，反正題目輸入的資料量不會超過他規定的最大值\(max_n\)

3. 狀態轉移(state transition)

根據前面求出的遞迴關係式，設定基本的子問題答案，再根據實作方法設計「轉移式」的表示法

如果沒有設定基本的子問題答案，你根本沒有推移子問題的起點(或終點)

將轉移式對應遞迴關係式，程式的實作方法不同，轉移式寫法就不同

//初始子問題答案設定(initialize)
f[1]=1;
f[2]=1;
//轉移式(之後要根據實作方法調整轉移式的表示法)
f[n]=f[n-1]+f[n-2];

4. 找到原問題的答案

根據你定義子問題及狀態轉移的方法，推理答案會出現在陣列的哪一格

第\(i\)項會放在第\(i\)格，所以答案在陣列第\(n\)格

cout<<f[n];

釐清以上四點後就可以開始實作程式碼了，實作方式分兩種

• top down
  使用遞迴由「原問題」推回「基本狀態」
• bottom up
  使用迴圈由「基本狀態」推至「原問題」

用top down的方式比較好思考，但用bottom up的執行時間比較短，所以建議大家先用top down寫寫看，再想要怎麼轉成bottom up

top down

top down 是先問原問題的答案，為了尋求原問題的答案，使用遞迴回推其子問題的答案，當所有衍生出的子問題都推至「基本狀態」後，便能得解

3. 轉移式設計為 return c[n]=遞迴式 ;

c[1]=0;
int t1=topdown(n-1)+abs(h[n]-h[n-1]);//f(n-1)+樓差
int t2=topdown(n-2)+abs(h[n]-h[n-2]);//f(n-2)+樓差
return c[n]=min(t1,t2);

#include <bits/stdc++.h>
using namespace std;
int n;
const int max_n=1e5+1;
const int max_v=1e4;
const int inf=1<<30;//不會落在答案範圍內
int h[max_n];
int c[max_n];
 
int topdown(int n){
	//終止條件:起點<=第0塊石頭，不可能發生
    //所以去掉這個選項->給出一個比所有可能答案都高的值
	if(n<1) return inf;
	if(c[n]==inf){//3.轉移式
		int t1=topdown(n-1)+abs(h[n]-h[n-1]);//f(n-1)+樓差
		int t2=topdown(n-2)+abs(h[n]-h[n-2]);//f(n-2)+樓差
		return c[n]=min(t1,t2);//記得return的時候要記憶化
	}
	return c[n];//算過的子問題的值不會是inf，直接套答案
}
 
int main() {
	for(int i=1;i<=n;i+=1){
		cin>>h[i];
		c[i]=inf;
	}
	c[1]=0;//基本的子問題答案
	cout<<topdown(n)<<'\n';
	}
	return 0;
}

bottom up

bottom up 藉由基本的子問題答案，使用for迴圈一步步組合成母問題的答案，當組合出原問題的答案，便能得解

3. 轉移式設計為 c[n]=遞迴式 ;

c[1]=0;
int t1=c[i-1]+abs(h[i]-h[i-1]);
int t2=c[i-2]+abs(h[i]-h[i-2]);
c[i]=min(t1,t2);

#include <bits/stdc++.h>
using namespace std;
int n;
const int max_n=1e5+1;
const int max_v=1e4;
const int inf=1<<30;//不會落在答案範圍內
int h[max_n];
int c[max_n];
 
int main() {
    for(int i=1;i<=n;i+=1){
        cin>>h[i];
    }
    c[1]=0;
    c[2]=abs(h[2]-h[1]);
    for(int i=3;i<=n;i+=1){
        int t1=c[i-1]+abs(h[i]-h[i-1]);
        int t2=c[i-2]+abs(h[i]-h[i-2]);
        c[i]=min(t1,t2);
    }
    cout<<c[n]<<'\n';
    return 0;
}
 

看起來這方式行得通。但要如何尋找每個狀態下的最佳解呢?
這時，我們可以連同其他重量的選擇也找好。
雖然我們無法從上個重量的答案推知下個重量的答案。
但是，藉由記錄每個重量，當前w的最佳解可以變成物品價值加上\(W_{重量差值}\)的最佳解，省去直接窮舉的時間。

weight: 1 2
value: 1 3
W: 5

遞迴式:
這裡區分一下: 物品價值\(v_i\), \(w_i\) 每個重量最佳解\(a_w\)
\(a_w\) = \(max(a_w, v_i+a_{w-w_{i}})\)

狀態轉移:
每當有新物品進來時，掃過陣列一遍，對每個重量最佳解進行更新。但還需要另一個陣列紀錄原陣列答案。

#include <bits/stdc++.h>
using namespace std;
 
int const MaxW = 1e6;
 
vector<pair<int, int>> vec;
int N, W;
int arr[2][MaxW+1];
int ans = 0;
 
bool cmp(pair<int, int> a, pair<int, int> b){
	
	if (a.first != b.first)
		return (a.first < b.first);
	else
		return (a.second < b.second);
	
}
 
 
int main(){
    stringstream ss1, ss2;
    string s1,s2;
    
    getline(cin, s1);
    ss1 << s1;
    
    string x;
    int idx = 0, a;
    int nowi = 0, nxti = 1;
    while (ss1 >> x){
        a = stoi(x);
        vec.push_back({a, 0});
    }
    
    getline(cin, s2);
    ss2 << s2;
 
    while (ss2 >> x){
        a = stoi(x);
        vec[idx++].second = a;
    }
    
    cin >> W;
    N = vec.size();
    sort(vec.begin(), vec.end(), cmp);
    
    
    //for (int i=0;i<N;i++){
    //	cout << vec[i].first << ' ' << vec[i].second << endl;
    //}
    memset(arr, 0, sizeof(arr));
    
    for (int n=0;n<N;n++){
    	for (int w = 1;w<=W;w++){
    		if (vec[n].first > w)continue;
    		arr[nxti][w] = max(arr[nowi][w], arr[nowi][w - vec[n].first]+vec[n].second);
    	}
    	swap(nowi, nxti);
    }
    
    cout << arr[nowi][W] << endl;
    
    return 0;
}