題目出處

801 · Backpack X

難度

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 使用的金錢 (表示我們目前用多少錢去換)

Reference

• 背包问题X · Backpack X