An Integer Representation Problem with Application to Postage Stamp Problem

一個可應用於連續郵資問題的整數表示問題

鄭延琮(Yen-Tsung Cheng)

指導教授 ： 李端興

國立清華大學/電機資訊學院/資訊工程學系/碩士(2009年)

摘要

Postage stamp problem is a famous, classic, and old problem which appears on
many books related to algorithm and programming skill . Here is its' description:
There are N kinds of stamps whose value to be printed on them is still unknown;
the space on each envelope is limited, and there are only k stamps can be attached on
it. How to print the value on each kind of stamps to allow the widest choice of value
to be made up from $1?
Note that Postage stamp problem can be viewed as a maximum consecutive in-
teger representation problem. Except for brute force algorithm, there is no explicit
algorithm to solve Postage stamp problem so far. However, if we specify the or-
der of choosing stamps to be attached when we want to make up some value on
the envelope, this problem can be solve by a greedy algorithm whose complexity is
O((N + k)minfN;kg). We then proof it can actually nd the optimal solution. Besides
Postage stamp problem, this greedy algorithm also have some other applications in-
cluding building optical queues, node symmetric chordal ring

關鍵字

連續整數 ； 演算法

並列摘要

連續郵資問題是一個在許多介紹演算法與程式技巧中常出現有
名、經典、古老的問題。問題的敘述如下：
有N 種郵票，面額還尚待確定。又因為信封上的空位有限，每封
信封上只能貼最多k 張郵票，那麼如何去選定這N 張郵票的面額，使
得我們能夠在信封上從1 塊錢開始連續貼出來的金額能夠最大?
連續郵資問題可以被視為一個最大連續整數表現問題。目前除了
暴力演算法(brute force algorithm)並無明確的演算法可以解決該問題。
然而如果限定郵票被選取的順序，我們在這裡將會介紹一種時間複雜
度為O((M+k)min{M, k})的貪婪演算法(greedy algorithm)間以解決郵票問題。
我們也將會證明該演算法的正確性，並且說明一些其他的應用：如建
造某些光佇列(optical queue)、點對稱弦環(node symmetric chordal
ring)。

並列關鍵字

integer representation

參考文獻

[1] W. Lunnon, A postage stamp problem," in Comput. J., vol. 12, pp. 377{380,

[3] C.-C. Chou, C.-S. Chang, D.-S. Lee, and J. Cheng, A necessary and sucient

[4] J. Cheng, Constructions of fault tolerant optical 2-to-1 fo multiplexers,"

[5] J. Cheng, C.-S. Chang, T.-H. Chao, D.-S. Lee, and C.-M. Lien, On constructions

of optical queues with a limited number of recirculations," in INFOCOM 2008.