在二城國小服替代役的時候，學校決定不再買進 1 元的郵票。雖然多了 3 元郵票會減少郵 票的使用量，也不會有湊不出正確郵資的問題，但是要怎麼貼郵票變成比較需要動腦筋的問 題。因為懶得每一次都自己動腦，就決定自己寫一個小程式來幫忙解決囉。給定一筆郵資， 程式將會決定不同種類的郵票要怎麼分配張數，可以達到郵票張數最少的組合。
選擇可用的郵票種類 | |
提供其他郵票種類請用空白鍵分開(例如："12 32")。重複超過一次，小於零，不是整數的郵票種類將會被忽略。 | |
函件資費 | |
計算結果
---
More about this tool
The program uses the naive dynamic programming approach to solve this problem. It assumes that:
- All types of stamps are infinitely possible
- All types of stamps and all target prices are simple integers
This reduces our question to the Change-Making Problem, rather than having to tackle a complete Knapsack Problem. Since a naive approach to dynamic programming is used, for a given total n the programs opens an integer array of size n. The program thus hard caps the total to be smaller than 10000, to avoid excessive memory usage while covering all likely postal fee. I know there are ways to extend this problem using the least common factor of stamp types, but I would be difficult to generalize when one day I decide to include the functionality of finite stamps.
List of known issues (and potential work around)
- No support for legacy stamp type NTD 3.5. In the meantime, use 7 as an additional stamp type and see if you can get better results.
- No support of stamp values greater than 10000. Until I find a better way of generalizing the solution, this would not be addressed.
- No support for finite stamp values, so if you are stuck with only two NTD 3 stamps, and wanted to check if you can still pay your fees using your NTD 5 and NTD 25 stamps, this is not the program for you. This functionality will not be implemented in the near future.
- Output format feels lack-luster. Not sure what could be done, any advice would be appreciated.