minz的筆記本

# DP跟divide and conquer差在哪 **分而治之法 (Divide and Conquer)** 如果問題很大，我們就把問題**分解成較小的子問題**，然後分別解決這些子問題。一旦所有的子問題都解決了，我們就把所有子問題的解決方案組合起來，找到大問題的解決方案。分治法的限制是子問題應該與原問題屬於同一類型。例如，如果主要問題是排序，那麼子問題也應該是排序。分治法的策略本質上是遞迴的。 動態規劃(**Dynamic Programming**) 則是將優化問題分解成更簡單的子問題，並**存儲**每個子問題的解決方案，以便每個子問題只需要解決一次。一旦所有的子問題都解決了，我

# 背包問題 背包問題（Knapsack Problem）是一個經典的優化問題，屬於組合優化問題的一種，有一個固定容量的背包和一組具有不同價值和重量的物品，我們需要在限制背包容量的條件下，選擇最佳的物品組合，使得**總價值最大化**，可以使用**動態規劃**、**貪婪算法**來找到最佳解。 背包問題可以分為兩種主要的變體： 1. 0/1 背包問題（0/1 Knapsack Problem）：每個物品要麼全部放入背包，要麼完全不放入背包，**無法將物品分割**為部分放入。 2. 分數背包問題（Fractional Knapsack Problem）：每個物品**可以按比例分割**，可以將物

# call by value (傳值) - 在Call-by-Value中，函式的參數是被傳遞值的**副本**。 - 在函式內部，對參數的修改不會影響到原始的變數。 :::info ### call by address (傳位置) - 傳了實際的記憶體位置進去function - 也是`call by value`的變形，但傳遞的是**記憶體地址**。 - 在函式內部，通過指標可以修改原始變數的值。 ::: # call by reference (傳參考) - 在Call-by-Reference中，函式的參數接受原始變數的參考（或記憶體位置）。 - 在函式內部，對參數的修

# 互斥和獨立事件 **互斥事件**指的是兩個或多個事件不可能同時發生的情況。 如果事件 A 發生，那麼事件 B 就不可能發生，且反之亦然。 數學上，兩個互斥事件 A 和 B 的概率滿足 P(A ∩ B) = 0，**即它們的交集為空集**。 例如，擲一個骰子，事件 A 是出現奇數點數，事件 B 是出現偶數點數。 由於奇數和偶數是互斥的，因此在一次擲骰子的結果中，不能同時出現奇數和偶數。 因此，事件 A 和事件 B 是互斥事件。 --- **獨立事件**指的是兩個或多個事件的發生與其他事件的發生無關。 如果事件 A 發生與否**不會影響**事件 B 發生的概率。 數學上，獨立事件 A

- stable sorting : 相同的值排序後順序皆一樣 - unstable sorting : 相同的值排序後順序可能會不一樣 # 初階排序 ```cpp 排序演算法 #include <iostream> #include <vector> #include <algorithm> using namespace std; // Bubble Sort mark:3-4 void bubbleSort(vector<int>& arr) { int n = arr.size(); for (int i = 0; i < n - 1; i++) {