# 背包問題
背包問題（Knapsack Problem）是一個經典的優化問題，屬於組合優化問題的一種，有一個固定容量的背包和一組具有不同價值和重量的物品，我們需要在限制背包容量的條件下，選擇最佳的物品組合，使得總價值最大化，可以使用動態規劃、貪婪算法來找到最佳解。
背包問題可以分為兩種主要的變體：
- 0/1 背包問題（0/1 Knapsack Problem）：每個物品要麼全部放入背包，要麼完全不放入背包，無法將物品分割為部分放入。
- 分數背包問題（Fractional Knapsack Problem）：每個物品可以按比例分割，可以將物品的一部分放入背包。
假設有一個可放入總重量為 10 的背包，我們有以下物品可供選擇：
- 物品 1：價值 60，重量 4，價值 / 重量 = 15
- 物品 2：價值 80，重量 5，價值 / 重量 = 16
- 物品 3：價值 100，重量 8，價值 / 重量 = 12.5
- 0/1 背包問題：
最佳的物品組合是將物品 2 和物品 1 放入背包，總價值為 140。
- 分數背包問題：
最佳的物品組合是將物品 2 和物品 1 完全放入背包，物品 3 的一部分（重量為 1）放入背包，總價值為 152.5。
這是因為物品 2 的價值重量比最高，而物品 1 的價值重量比次之，物品 3 的價值重量比最低，
因此我們先選取物品 2 和物品 1，再選取物品 3 的一部分。
# 尤拉函數
尤拉函數（Euler's function），也稱為歐拉函數或歐拉 φ 函數。
- 用來計算小於或等於給定正整數的自然數中與該正整數
互質的數的個數。
尤拉函數的符號表示為 φ(n)，其中 n 是一個正整數。
尤拉函數的計算方法基於歐拉定理，它指出若 a 和 n 是互質的正整數，則 a 的尤拉函數值 φ(n) 等於小於或等於 n 的正整數中與 n 互質的數的個數。
範例：
假設我們要計算 φ(8)。首先，列出小於或等於 8 的正整數：1、2、3、4、5、6、7、8。
然後，我們找出與 8 互質的數，即與 8 沒有共同因數的數。
在這個例子中，與 8 互質的數有：1、3、5、7。因此，φ(8) = 4，表示小於或等於 8 的正整數中，有 4 個與 8 互質的數。
