撰寫動態算法

6.1 開發動態算法的基本步驟。

開發動態算法的基本步驟

1. 定義子任務：

把一個問題分解成可以獨立解決的較小子任務。這些子任務應該是重疊的，以便可以重用先前計算的結果。

2. 識別狀態：

確定解決問題時可能出現的所有狀態。狀態應描述從一個步驟轉移到下一步所需的所有信息。

3. 制定遞推關係：

確定當前狀態的解決方案如何依賴於之前狀態的解決方案。這種關係應該表達如何利用子任務的解決方案來獲得最佳解決方案。

4. 定義基本情況：

確定那些解決方案已知不需要進一步計算的基本情況。

5. 填寫表格：

建立一個表（通常是數組或矩陣）來存儲所有子任務的解決方案。利用遞推關係和基本情況從下往上或從上往下填寫表格。

6. 優化（記憶化）：

如果使用遞歸方法，則添加記憶化來保存子任務的結果並避免重複計算。

動態算法的時間和空間複雜度

時間複雜度：

• 動態算法的時間複雜度通常表達為子任務數量和計算每個子任務所需的時間。
• 大多數情況下，時間複雜度是 O(n) 或 O(n^2)，其中 n 是輸入數據的大小。

空間複雜度：

• 空間複雜度取決於需要存儲的狀態數目。
• 在某些情況下，可以通過優化來減少空間複雜度，如把所佔用的內存減少到 O(n) 或 O(1)。

6.2 背包問題。

背包問題 是 經典的組合優化問題，出現在包括計算機科學、經濟學和物流管理等多個領域。這個問題的主要目標是有效利用有限資源。

描述背包問題

有一個可以承受特定重量 W 的背包，還有 n 個物品，每個物品都有特定的重量 wt[i] 和價值 val[i]。 需要確定應該選擇哪些物品才能在不超過背包重量限制的情況下使它們總價值最大化。

背包問題的類型

1. 0/1 背包問題 (0/1 Knapsack Problem):

每個物品可以選擇拿或者不拿（不能部分拿）。

2. 分數背包問題 (Fractional Knapsack Problem):

每個物品可以分成任意部分。

3. 多重背包問題 (Multiple Knapsack Problem):

有多個背包具有不同的重量限制。

0/1 背包問題的算法表示：

遞推關係：

對於每個物品 i 和每個可能的重量 w（從 0 到 W），最佳解決方案可以如下表達：

• 如果物品 i 不放入背包，那麼最佳值等於 i − 1 個物品和重量 w 的最佳值。
• 如果物品 i 放入背包，那麼最佳值等於這個物品的價值加上 i − 1 個物品和重量 w − wt[i] 的最佳值。

時間和空間複雜度

時間複雜度：

此算法的時間複雜度是 O(nW)，其中 n 是物品的數量，而 W 是背包的容量。這是因為需要填寫一個大小為 n × W 的表格。

空間複雜度：

空間複雜度也是 O(nW)，因為需要一個表格來存儲中間結果。

0/1 背包問題的實現示例

def knapsack(W, wt, val, n):
    # 創建表格來存儲中間值
    dp = [[0 for x in range(W + 1)] for x in range(n + 1)]
        
    # 從底向上填寫 dp 表格
    for i in range(n + 1):
        for w in range(W + 1):
            if i == 0 or w == 0:
                dp[i][w] = 0
            elif wt[i - 1] <= w:
                dp[i][w] = max(val[i - 1] + dp[i - 1][w - wt[i - 1]], dp[i - 1][w])
            else:
                dp[i][w] = dp[i - 1][w]
        
    return dp[n][W]
        
# 使用示例
val = [60, 100, 120]
wt = [10, 20, 30]
W = 50
n = len(val)
print(f"最大背包價值: {knapsack(W, wt, val, n)}")
        

6.3 硬幣兌換問題。

硬幣兌換問題 是 經典的動態規劃問題，涉及如何從給定面值的硬幣集合中找出組成一定金額的最小數量的硬幣或方法數。這個問題有兩個主要變體：

最小硬幣數量 (Minimum Coin Change Problem):

找出能夠組成給定金額的最小硬幣數量。

兌換方法數量 (Number of Ways to Make Change):

找出用給定硬幣集合組成給定金額的不同方法數。

變體 1. 最小硬幣數量

問題描述

已知：

• 有無限數量的特定面值的硬幣。
• 目標金額 S。

需要：

• 找出組成金額 S 的最小硬幣數量。

使用動態規劃的解決方案

遞推關係：

• 設 dp[i] 表示組成金額 i 所需的最小硬幣數量。
• 對於每個硬幣 c，如果 i ≥ c，那麼：dp[i] = min(dp[i], dp[i − c] + 1)

基本情況：

• dp[0] = 0（對於金額 0，不需要硬幣）。

時間和空間複雜度：

• 時間複雜度：O(n ⋅ S)，其中 n 是硬幣面額的數量， S 是目標金額。
• 空間複雜度：O(S)，因為需要一個數組來存儲從 0 到 S 的每個金額的最小硬幣數量。

Python實現示例

def min_coins(coins, S):
    dp = [float('inf')] * (S + 1)
    dp[0] = 0
        
    for i in range(1, S + 1):
        for coin in coins:
            if i >= coin:
                dp[i] = min(dp[i], dp[i - coin] + 1)
        
    return dp[S] if dp[S] != float('inf') else -1
        
# 使用示例
coins = [1, 2, 5]
S = 11
print(f"對於金額 {S} 的最小硬幣數量: {min_coins(coins, S)}")
        
        

硬幣兌換問題展示了動態規劃的靈活性。它被用於教學和研究算法技術，因為它顯示了如何使用遞推關係和基本情況來有效解決問題。