資料結構(python) —— 【34: 動态規劃之鋼條切割問題】

鋼條切割問題

1. 問題

某公司出售鋼條，出售價格與鋼條長度之間的關系如下表:

問題:現有一段長度為n的鋼條和上面的價格表，求切割鋼條方案，使得總收益最大。

2. 思路

思考: 長度為n的鋼條的不同切割方案有幾種?

有 2 n − 1 2^{n-1} 2n−1種，因為有 n − 1 n-1 n−1個可以切割的地方，每個位置都有切與不切兩種選擇，是以是 2 n − 1 2^{n-1} 2n−1種，但是這種方法不太合适，因為如果n太大的時候，切割方案會指數爆炸，效率不高。

2.1 最優子結構

    昨天有講動态規劃，動态規劃(DP)的思想 = 最優子結構(遞推式) + 重複子問題，那麼我們可以看看這道題目的最優子結構:

1. 可以将求解規模為n的原問題，劃分為規模更小的子問題:完成一次切割後，可以将産生的兩段鋼條看成兩個獨立的鋼條切個問題。
2. 組合兩個子問題的最優解，并在所有可能的兩段切割方案中選取組合收益最大的，構成原問題的最優解。
3. 鋼條切割滿足最優子結構:問題的最優解由相關子問題的最優解組合而成，這些子問題可以獨立求解。

最優子結構(大的問題切割為小的子問題，如果子問題有最優解并且這些最優解解能算大問題的解，即最優子結構)

2.2 遞推式

我們再來看看這道問題的遞推式:

設長度為n的鋼條切割後最優收益值為rn，可以得出遞推式:

r n = m a x ( p n , r 1 + r n − 1 , r 2 + r n − 2 , . . . , r n − 1 十 r 1 ) r_n=max(p_n,r_1 +r_{n-1},r_2+r_{n-2},...,r_{n-1}十r_1) rn​=max(pn​,r1​+rn−1​,r2​+rn−2​,...,rn−1​十r1​)

第一個參數 p n p_n pn​表示不切割，其他 n − 1 n-1 n−1個參數分别表示另外 n − 1 n-1 n−1種不同切割方案，對方案 i = 1 , 2... n − 1 i=1,2...n-1 i=1,2...n−1，将鋼條切割為長度為 i i i和 n − i n-i n−i兩段，方案i的收益為切割兩段的最優收益之和，考察所有的 i i i，選擇其中收益最大的方案！

3. 代碼

從遞推式，我們想到可以用遞歸求解！有結束條件，又是調用自身

'''
TOPIC: 鋼條切割: 遞歸實作
author: Blue
time: 2020-08-19
QQ: 2458682080
'''

# 價格清單，下标即為長度
p = [0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30]


def cut_rod_recurision_1(p, n):
    if n == 0:
        return 0
    else:
        res = p[n]
        for i in range(1, n):
            res = max(res, cut_rod_recurision_1(p, i) + cut_rod_recurision_1(p, n - i))
            # 遞歸2次，是以慢
        return res
print(cut_rod_recurision_1(p, 10))
           

結果為:

30

，即當鋼條長度n=10時，最大總收益為30！

4. 思路改進

昨天的部落格裡說到了，當n變大時，遞歸的效率其實也不高，那麼有什麼方法可以進行改進呢？我們想，上面的遞推式，我們取的是 m a x ( r i + r n − i ) max(r_i +r_{n-i}) max(ri​+rn−i​)，即算當

i

确定時，就要進行兩次遞歸，那麼是不是可以減少遞歸的次數呢？

這裡我們就進行改進：

1. 從鋼條的左邊切割下長度為i的一段，隻對右邊剩下的一段繼續進行切割，左邊的不再切割
2. 遞推式簡化為 r n = max ⁡ 1 < j ≤ m ( p i + r n − i ) r_n=\max\limits_{1<j\leq m}(p_i+r_{n-i}) rn​=1<j≤mmax​(pi​+rn−i​)
3. 不做切割的方案就可以描述為:左邊一段長度為n，收益為 p n p_n pn​，剩餘一段長度為0，收益為 r 0 r_0 r0​=0。

這樣對于每一個i，我們就減少了遞歸的次數，增加了效率！

5. 代碼改進

# 簡化後的算法
def cut_rod_recurision_2(p, n):
    if n == 0:
        return 0
    else:
        res = 0
        for i in range(1, n+1):
            res = max(res, p[i] + cut_rod_recurision_2(p, n-i))  # 遞歸一次，是以快
        return res
           

6. 思路再改進

其實我們思路改進後，還是用到了遞歸，隻不過是減少了遞歸的使用次數而已，是以當n過大時，算法還是無法承受，效率不高。我們之前的兩種方法，改進前以及改進後，都用到了遞歸，遞推式分别為:

r n = m a x ( p n , r 1 + r n − 1 , r 2 + r n − 2 , . . . , r n − 1 十 r 1 ) r_n=max(p_n,r_1 +r_{n-1},r_2+r_{n-2},...,r_{n-1}十r_1) rn​=max(pn​,r1​+rn−1​,r2​+rn−2​,...,rn−1​十r1​)

r n = max ⁡ 1 < j ≤ m ( p i + r n − i ) r_n=\max\limits_{1<j\leq m}(p_i+r_{n-i}) rn​=1<j≤mmax​(pi​+rn−i​)

可以發現，這兩種方法都是自上而下的切割方法。什麼叫做自上而下的切割方法呢？就是把長度為n的進行切割為兩段，再分别計算兩段的最優價值，就這樣，一步一步切割，一步一步計算，最後到不能切割為止，得到結果！時間複雜度為 O ( 2 n ) O(2^n) O(2n)!

那這裡，我們就提出了 動态規劃(DP)的思路 ：

自底向上的方法: 從短到長，把長度從0~n的鋼條最優價格求出來，因為每次求出長度後都用清單儲存，是以計算後面的長度時，直接從清單裡取出相應切割方案對應的價值，相加即可，不需要遞歸，大大增加了效率！

7. 代碼再改進

def cut_rod_dp(p, n):
    r = [0]
    for i in range(1, n+1):  # 下标i對應的數字就是長度為n=i的鋼條的最優價格，是以i從1開始，把長度從1~n的鋼條最優價格求出來
        res = 0
        for j in range(1, i+1):  # 求當n确定時，利用遞推式求出此時的最優價格
            res = max(res, p[j] + r[i - j])
        r.append(res)
    return r[n]
           

思路很簡單，代碼也很簡單！

當然，有了最大價值，我們還需要知道切割方案：

'''
TOPIC: 鋼條切割: 自頂向下實作
author: Blue
time: 2020-08-19
QQ: 2458682080
'''

# 重構解
def cut_rod_extend(p, n):
    r = [0]
    s = [0]
    for i in range(1, n+1):  # 下标i對應的數字就是長度為n=i的鋼條的最優價格，是以i從1開始
        res_r = 0  # 記錄價格的最大值
        res_s = 0  # 記錄價格最大值對應方案的左邊不切割部分的長度
        for j in range(1, i+1):
            if p[j] + r[i - j] > res_r:
                res_r = p[j] + r[i - j]
                res_s = j
        r.append(res_r)
        s.append(res_s)
    return r[n], s


# 擷取切割方案
def cut_rod_solution(p, n):
    r, s = cut_rod_extend(p, n)
    ans = []
    while n > 0:
        ans.append(s[n])
        n -= s[n]
    return ans
           

所有代碼為:

# 自底向上的方法
def cut_rod_dp(p, n):
    r = [0]
    for i in range(1, n+1):  # 下标i對應的數字就是長度為n=i的鋼條的最優價格，是以i從1開始，把長度從1~n的鋼條最優價格求出來
        res = 0
        for j in range(1, i+1):  # 求當n确定時，利用遞推式求出此時的最優價格
            res = max(res, p[j] + r[i - j])
        r.append(res)
    return r[n]

# print(c2(p, 20))
# print(cut_rod_dp(p, 20))

# 重構解
def cut_rod_extend(p, n):
    r = [0]
    s = [0]
    for i in range(1, n+1):  # 下标i對應的數字就是長度為n=i的鋼條的最優價格，是以i從1開始
        res_r = 0  # 記錄價格的最大值
        res_s = 0  # 記錄價格最大值對應方案的左邊不切割部分的長度
        for j in range(1, i+1):
            if p[j] + r[i - j] > res_r:
                res_r = p[j] + r[i - j]
                res_s = j
        r.append(res_r)
        s.append(res_s)
    return r[n], s


# 擷取切割方案
def cut_rod_solution(p, n):
    r, s = cut_rod_extend(p, n)
    ans = []
    while n > 0:
        ans.append(s[n])
        n -= s[n]
    return ans


r, s = cut_rod_extend(p, 20)
print(s)
print(cut_rod_dp(p, 20))

           

結果為:

[0, 1, 2, 3, 2, 2, 6, 1, 2, 3, 10]  # 切割方案
30  # 最大價值
           

鋼條切割問題——自底向上遞歸實作

時間複雜度O(n^2)

8. 總結

鋼條切割問題——動态規劃解法

遞歸算法由于重複求解相同子問題，效率極低

動态規劃的思想:

1. 每個子問題隻求解一次，儲存求解結果
2. 之後需要此問題時，隻需查找儲存的結果

動态規劃問題關鍵特征

什麼問題可以使用動态規劃方法?

1. 最優問題
2. 最優子結構
   • 原問題的最優解中涉及多少個子問題
   • 在确定最優解使用哪些子問題時，需要考慮多少種選擇
3. 重疊子問題