找到一個數字是給定集合中兩個或更多數字的可能總和 - python

Question

辦公用品商店以5,8或24筆包裝銷售您最喜愛的筆類型。因此，例如，可以準確地購買13支鋼筆（一個包裝5個，另一個包裝8個），但不可能正好購買11支鋼筆，因爲沒有5,8的非負整數組合爲了確定是否有可能正好購買n筆，必須找到a，b和c的非負整數值，使得

5a + 8b + 24c = n

編寫一個稱爲numPens的函數，該函數接受一個參數n，如果可以購買5,8和24個包裝單位的組合，使得總筆數等於n，否則返回False，並返回True。

注意：這是一個在上半月進行的mid sem考試中提出的問題。我無法解決它，但仍在尋找解決方案。任何幫助將被接受。 python中的代碼或算法來解決它。謝謝

Answer 1

這聽起來很適合dynamic programming。

def numPens(n): 
    pen_sizes = [5, 8, 24] 
    results = [True] 
    for i in range(1, n+1): 
    results.append(any(i >= size and results[i - size] for size in pen_sizes)) 
    return results[n] 

這裏的關鍵見解是：

1. 0筆可以實現（平凡：每個大小爲0包）。
2. 如果我們已經知道少於n筆的答案，我們可以計算出是否可以得到n筆。

例如，假設我們已經知道0到9的答案，我們想知道我們是否可以得到10支筆。那麼，我們至少需要一個包才能這樣做。然後有3種情況需要考慮：

1. 5包+但是我們得到5筆，如果有可能得到5筆。
2. 一包8 +，但我們得到2筆，如果有可能得到2筆。
3. 24包+但我們得到-14筆，如果有可能得到-14筆。

最後一個是無意義的，所以如果（並且只有）有可能獲得5支筆或獲得2支筆，那麼獲得10支筆是可能的。因爲我們假設我們已經知道0到9的答案，所以我們可以解決這個問題（事實證明5筆是可能的，作爲5包，所以我們得出結論，10也是如此）。

因此，爲了讓自己處於我們總是有較小n值的答案的情況，我們從0開始顯而易見的答案。然後我們計算答案爲1（因爲我們的答案爲0已經，我們可以做到這一點）。然後我們計算2的答案（因爲我們已經有0和1了，我們可以做到這一點），等等，直到我們有了我們想要的n的答案。

這段代碼封裝了從以前的結果，結果的實際計算：它產生True如果有任何的包裝尺寸size爲這是有意義的買大小的包（沒有得到一個負數i - size ），而我們以前有 找到了一種方法來購買i - size筆。

any(i >= size and results[i - size] for size in pen_sizes) 

的代碼的其餘部分只是讓我們，導致results列表供以後使用，並最終返回的最終結果商店。