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

白話說就是針對「 優化問題 」將原始問題可以分解成多個子問題這些子問題的解可以被重複並利用子問題的解來解決原始問題～～

有一個固定容量的背包，以及一些物品，每個物品都有自己的價值和重量。我們的目標是將這些物品放入背包中，使得放入的物品的總價值最大，假設有一個背包容量為 10，並且有以下物品：
物品1：價值 60，重量 5
物品2：價值 50，重量 3
物品3：價值 70，重量 4
物品4：價值 30，重量 2
我們的目標是將這些物品放入背包中，使得放入的物品的總價值最大
這可以通過動態規劃來解決，創建一個二維表格，其中行表示可選擇的物品，列表示背包的容量，並在表格中填充相應的值～

    0   1   2   3   4   5   6   7   8   9   10
0   0   0   0   0   0   0   0   0   0   0   0
1   0   0   0   0   0   60  60  60  60  60  60
2   0   0   0   50  50  60  60  110 110 110 110
3   0   0   0   50  70  70  70  110 120 120 120
4   0   30  30  50  70  70  70  110 120 150 150

在這個表格中，每個格子的值代表了在相應的物品和背包容量下，可以獲得的最大價值。例如，第二行第六列的值 60 表示在只考慮第一個物品且背包容量為 5 時，可以獲得的最大價值
透過填充表格，我們可以找到最終的解，也就是表格的右下角值，這個值即為放入背包中物品的最大價值～

def knapsack(items, capacity):
    n = len(items)
    # 創建一個二維表格，初始化為0
    dp = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(1, capacity + 1):
            if items[i-1][1] <= w:
                dp[i][w] = max(items[i-1][0] + dp[i-1][w-items[i-1][1]], dp[i-1][w])
            else:
                dp[i][w] = dp[i-1][w]

    return dp[n][capacity]

# 測試案例
items = [(60, 5), (50, 3), (70, 4), (30, 2)]
capacity = 10
result = knapsack(items, capacity)
print("背包中物品的最大價值為:", result)

這個程式中，我們定義了一個 knapsack 函數，它接受物品列表和背包容量作為參數。函數使用一個二維表格 dp 來保存中間計算的結果，最終返回背包中物品的最大價值。