---
tags: Algorithm
---

# DIY Problem 2 - CH15 Dynamic Programming

吳柏毅與傅朋達盛行，你因為作業太多寫不完懶得出去買午餐。因此決定午餐要叫外送解決。假設你所在的外送區域總共有 m 家商店，這 m 家商店總共販賣了 n 種商品(每家商品的產品皆不完全相同，且每家店都至少供應了一種商品)。而如果你在某家店購買了商品，你就需要付這家店的運費(每家店運費可能不同)，而且不管你在這家店購買了多少的商品，運費都是一樣的(舉例來說，假設你在 A 店買了1 塊炸雞，需要付出 30 元的運費，那你在 A 店買了100塊炸雞，仍然只需要付 30 元的運費)。你現在手上只有 x 元，而且你想要全部花光，請寫出一種演算法，可以告訴他**如果把這 x 元全部花光，可以有幾種餐點組合**

### 輸入的資料有 :
1. `n` => 「商品的數量」
2. `m` => 「商店的數量」
3. `x` => 「目前有的錢」
4. `goods[n][2]` => 紀錄 n 種商品，存放的資料分別是 「此商品是由哪家店販賣的」(index = 1)，以及 「此商品售價是多少」 (index = 2)
5. `store[m]` => 紀錄 m 家商店， 存放的資料是 「此商店所需的運費」

### 解題思路:
使用 Dynamic Programming，因為這個問題可以拆分成許多子問題，而且會有許多重複的子問題。
例如:
假設我總共有 500 元，目前我在 A 店購買了兩個 50 元的商品 1 (運費 20 元)， 且在 B 店購買了三個 25 元 的商品 2 (運費 25 元)， 因為解題是利用迴圈解決，因此接下來的選擇只會是商品 3 ~ n。 在另一次組合中， 我在 A 店購買了一個 50 元的商品 1 (運費一樣為 20 元)， 且在 B 店購買了五個 25 元 的商品 2 (運費一樣為 25 元)。在這兩次目前的組合中，都已經選定好了商品 1 及 商品 2 的數量。而且剩餘的錢都是 280 元，那剩下要做的都會是 「以 280 元選取商品3 ~ n 的組合」，意即重複的子問題，因此，若利用Dynamic Programming ，就可以省去重複計算的困擾

### 先寫出遞迴過程中需要用到的資料結構與其意義:
1. `goods[n][3]` => 與原本輸入資料不同的是，多了第三維資料，其中存放的是 「目前的組合中有多少此商品」(index = 3)
2. `store[m][2]` => 與原本輸入資料不同的是，多了第二維資料，其中存放的是 「目前的組合中是否有選過此商店的商品」 (index = 2)
3. `table[n][x]` => DP 表格，紀錄「此子問題以往的最佳解」
5. `index` => 「目前看到第幾種商品」
6. `remain` => 「目前剩下多少錢」
7. `ans` => 「以目前的組合繼續選取商品下去，最後會有幾種組合滿足條件」

### Pseudo code

Buy(n, m, index, remain , store[m][2] , goods[n][3])  
    ans = 0      
    // 如果剩下的錢是 0 元，代表已經成功把原本的 x 元全部花完，因此組合多了一種
    if (remain == 0){     
        return 1
    }
    // 如果已經看完了全部 n 種商品，卻還有剩錢，表示這種組合並不符合條件
    elif (index >= n){
        return 0
    }
    // 如果已經計算過剩下組合可能的答案，就不用再計算一遍了(Dynamic Programming精神)
    if (table[index][remain] != -1){
        return table[index][remain]
    }
    // 如果目前的組合已經有這家商店的商品，就不用再付一次運費了
    elif (store[goods[index][1](哪家店)][2] == False){
        ans += Buy(index + 1, store[m][2],remain)
        store[goods[index][1](哪家店)][2] = True
        for (int i = 1; remain-store[goods[index][1](哪家店)][1] - goods[index][2]*i>= 0; i ++)
            ans += Buy(index + 1, store[m][2],remain - i * goods[index][2] )   
    }
    // 如果目前的組合沒有這家商店的商品，就需要付運費
    else{
        for (int i = 0 ; remain - i * goods[index][2] * i >= 0; i ++ )
            ans += Buy(index + 1, store[m][2], remain - i * goods[index][2] * i)
    }
    //紀錄下來剛剛算過的子問題會有多少答案
    table[index][remain] = ans
    return ans,

main (n, m, x,goods[n][2],store[m])
    // 預處理
    fill table[n][x] with -1 // 一開始沒有算過任何組合，先將 DP 陣列先初始化為未啟動狀態
    for i = 1 to n:        // 每個商品一開始購買的數量都是0
        goods[n].append(0)
    for i =  1 to m :     // 一開始沒有在任何一家店有想要買的商品
        store[m].append(False)
    ans = Buy (n, m, 0,x,store,goods) // 從第一種商品開始嘗試，且一開始有 x 元
    print("You have", ans, " kinds of combination")