題目出處
難度
medium
個人範例程式碼
class Solution:
"""
@param n: the money you have
@return: the minimum money you have to give
"""
def back_pack_x(self, n: int) -> int:
# write your code here
# 150, 250, 350 = 3, 5, 7 (//50)
prices = [3, 5, 7]
target = n // 50
dp = [price for price in range(target+1)] # 0,1,2,3...
for current_target in range(1, target+1):
for price in prices:
last_price = current_target - price
if last_price >= 0:
dp[current_target] = min(dp[current_target], dp[last_price])
rest = n % 50
return dp[-1]*50 + rest
算法說明
本題是背包系列問題的第 10 題，建議初學者可以從第一題開始去學：
第 1 題：最基本的背包問題，不重複 size，物品只有一個，計算組合可能性
第 2 題：最基本的背包問題，不重複 size，物品只有一個，計算最大價值
第 3 題：完全背包問題，有重複 size，物品無限數量，計算最大價值
第 4 題：有重複 size，物品無限數量，計算可能組合 ，「(1,2,3) 與 (2,3,1) 視為相同答案」
第 5 題：有重複 size，物品有限數量，計算可能組合 ，「(1,2,3) 與 (2,3,1) 視為相同答案」
第 6 題：有重複 size，物品無限數量，計算可能「排列」 ，也就是說「(1,2,3) 與 (2,3,1) 視為不同答案」
第 7 題：有重複物品，有限制物品數數量上限，問可能組合
第 8 題：有重複物品，有限制物品數數量上限，問最大價值
第 9 題：變化問題，有重複 size，計算機率
第 10 題：變化問題，只是把 size 面額提高
第 10 題，也是背包問題的變化題型，這題我們是變成單位比較大值，
我們替換成鈔票，面額直接是 150, 250, 350 去組合。
首先我們如果直接一個一個處理，時間會太浪費，
因此我們先取最大公因數 [150, 250, 350] = [3, 5, 7]
dp 儲存我們「剩餘的最小價格」。
外圈 for 我們選擇新的幣種，
內圈 for 我們想計算的總額，記得也要先取 //50，並保留 rest = %50。
最後務必記得回傳 「rest + dp[-1]*50」，一定要記得還有 rest 的部分！！
input handling
一同在 dp 內處理
Boundary conditions
用兩層 for 來控制搜尋範圍，
外層 for 我們選擇新的幣種 (表示我們擁有新幣種後，可能有的組合。)
內層 for 使用的金錢 (表示我們目前用多少錢去換)