適用重疊子問題性質問題來找到使某個目標函數最大化或最小化的值

白話說就是針對「 優化問題 」將原始問題可以分解成多個子問題這些子問題的解可以被重複並利用子問題的解來解決原始問題而這些問題具體取決於給定的約束條件來找到最佳解～～

「 背包問題 」的類型以及我們可能會選擇使用動態規劃或貪心算法來解決相應的問題。
可看看昨天內容～～DAY 15 「動態規劃（Dynamic Programming）」優化問題中的始祖Python程式碼撰寫～

• 0/1 背包問題：
  在這種情況下，物品要麼全部選擇（1），要麼全部不選擇（0），不能部分選擇。
  這是一個 NP 完全問題，並且通常需要使用動態規劃等方法來找到最佳解～
  白話就是說每個物品只能選擇一次，要麼選擇放入背包，要麼不選擇。這是一個布爾（二進制）決策問題～～
  假設你有一個背包，它的容量為 C，還有一系列的物品，每個物品都有自己的重量 w 和價值 v。你需要在背包的容量範圍內選擇物品放入背包，使得放入的物品總價值最大。

動態規劃解決這個問題的思路如下：

創建一個二維數組 dp，其中 dp[i][j] 表示前 i 個物品，在容量為 j 的背包下所能獲得的最大價值。
初始化 dp，將第一行和第一列設為0，因為在容量為0的背包下無法放入物品。
對於每一個物品，我們有兩種選擇：
選擇放入：如果 w[i-1]（第 i 個物品的重量）小於等於當前背包的容量 j，則可以考慮將這個物品放入背包中，這時的總價值為 v[i-1]（第 i 個物品的價值）加上前 i-1 個物品在容量為 j-w[i-1] 的背包下的最大價值，即 dp[i-1][j-w[i-1]]。
不選擇放入：如果將這個物品放入背包會超出容量，那麼只能不選擇放入，總價值為前 i-1 個物品在容量為 j 的背包下的最大價值，即 dp[i-1][j]。

於是，我們可以得到以下狀態轉移方程：

dp[i][j] = max(dp[i-1][j], v[i-1] + dp[i-1][j-w[i-1]]), if w[i-1] <= j
          dp[i-1][j],                               if w[i-1] > j
          

最終結果位於 dp[n][C]，其中 n 是物品的數量。

def knapSack(C, w, v, n):
    dp = [[0 for j in range(C+1)] for i in range(n+1)]
    
    for i in range(n+1):
        for j in range(C+1):
            if i == 0 or j == 0:
                dp[i][j] = 0
            elif w[i-1] <= j:
                dp[i][j] = max(v[i-1] + dp[i-1][j-w[i-1]], dp[i-1][j])
            else:
                dp[i][j] = dp[i-1][j]
    
    return dp[n][C]

# 測試
C = 10
w = [2, 3, 4, 5]
v = [3, 4, 5, 6]
n = len(w)

result = knapSack(C, w, v, n)
print("最大價值為:", result)

這段程式碼將輸出 最大價值為: 7，表示在背包容量為 10 時，選擇一些物品放入背包可以獲得的最大價值為 7