---
# System prepended metadata

title: 'ADA 5.3: Stamp Problem'
tags: [ADA 5.3, StampProblem 郵票問題]

---

###### tags: `ADA 5.3` `StampProblem 郵票問題`

# ADA 5.3: Stamp Problem

### 初步認識
#### 在不同數量面額的郵票內，湊出符合郵資的郵票，並且需要透過最少張數完成。

##  Recursive 暴力解
#### 1+min(Sn-3, Sn-5, Sn-7, Sn-12) Sn為現有所需郵資

### 公式 For Recursive
![](https://i.imgur.com/AhhesIh.png)
#### v:    現有郵票(1張7元, 3張9元, 2張10元...)
#### n:    所需郵資
#### r_min:所需最小郵票數量
#### r:    各郵票張數

#### 透過暴力解時間複雜度為k的n次方


##  OPT 最佳解
#### 郵資為S(i)最少需要S(n)郵票，現有k種郵資

![](https://i.imgur.com/kNK3bMQ.png)

#### Si = 1+Si-v1 (暫時視為1為某張郵票的郵資)


## 透過Bottom-up貼出郵票
![](https://i.imgur.com/F7M7sOm.png)


### 公式 For OPT
![](https://i.imgur.com/aUwVlEf.png)





![](https://i.imgur.com/FGXg5n6.png)

#### 時間複雜度(kn)

---


## 解題疑問

#### 若都數偶數郵票如何解奇術郵資？有超過就好？



