郵票拼圖

Question

我的老師給了我一套問題，讓我們考慮遞歸。其中之一，我們被賦予一個價值（郵資的成本）和一個可用的郵票列表。該練習涉及編寫一個遞歸函數，該函數返回郵票的最小長度列表，其總數等於郵資的總和值。

解決這個問題的正確方法就是讓程序比較每一種可能性並返回最小長度的程序。如果是這種情況，我不確定如何爲它編寫程序，更不用說使用遞歸，因爲我一般都是Python和編程的新手。根據教師提供的線索，我想出了這樣的事情：

stampList=[1,4,7] 
postage=10 

def pickStamps(postage): 
    if postage==0: #base case 1 
     return "" 
    if postage<0: #base case 2 
     return none 
    else: 
     x=postage 
     for i in range(len(stampList)-1): 
     x=x-stampList[i] 
     return pickStamps(x) 

我試圖有蟒蛇開始郵資的價值，減去結合每種面額才能到零，但我不確定如何將每種可能性都列入清單。在問題中提出，編寫另一個函數可能是明智的，該函數接受一個列表列表的參數，並返回列表中最小長度元素的索引，但我不確定如何實現該列表。有人能告訴我如何編寫這樣的代碼或解釋解決這個問題的最佳方法嗎？謝謝！

Answer 1

試想一下，你有已經工作的功能：

def pick_stamps(postage): 
    '''Returns list of stamps needed to cover postage''' 

鑑於你有這個功能，你可以用它來實現您的版本：

def my_pick_stamps(postage): 
    if postage == 0: 
     return [] 
    else: 
     stamp = max(stamp for stamp in stamps 
        if stamp <= postage) 
     return [stamp] + pick_stamps(postage - stamp) 

當然，一旦你實現你可以使用你的版本，並用my_pick_stamps代替pick_stamps。

Answer 2

def ways(wallet, stamp_values, postage): 
    amount = sum(wallet) 
    if amount == postage: 
     return [wallet] 
    elif amount > postage: 
     return [] 
    else: 
     next_stamp = wallet[-1] if wallet else max(stamp_values) 
     new_stamps = stamp_values[stamp_values.index(next_stamp):] 
     gen = (ways(wallet + [c], new_stamps, postage=postage) for c in new_stamps) 
     return sum(gen, []) 

試駕：

>>> combos = ways([], stamp_values=(7,4,1), postage=10) 
>>> combos 
[[7, 1, 1, 1], 
[4, 4, 1, 1], 
[4, 1, 1, 1, 1, 1, 1], 
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]] 
>>> min(combos, key=len) 
[7, 1, 1, 1] 

注意該解決方案實際上是在你的例子非唯一，即7,1,1,1和4,4,1,1都是相同的長度。假設我們有一個價值3的新郵票，我們應該期望看到一個獨特的解決方案，然後（7 + 3 == 10與兩個郵票）。

>>> ways([], stamp_values=(7,4,3,1), postage=10) 
[[7, 3], 
[7, 1, 1, 1], 
[4, 4, 1, 1], 
[4, 3, 3], 
[4, 3, 1, 1, 1], 
[4, 1, 1, 1, 1, 1, 1], 
[3, 3, 3, 1], 
[3, 3, 1, 1, 1, 1], 
[3, 1, 1, 1, 1, 1, 1, 1], 
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]]