著者

飯田 浩志

出版者

小樽商科大学ビジネス創造センター

雑誌

Discussion paper series

巻号頁・発行日

vol.101, pp.1-7, 2005-07

---

整数ナップサック問題は, よく知られた0?1 ナップサック問題の数ある拡張の一つである.0?1 ナップサック問題の拡張ゆえに, 整数ナップサック問題も容易には解けない問題であり, 分枝限定法・動的計画法等の一般的な枠組みを用いて解かざるを得ない. しかしその一方で, ある特殊な場合には多項式時間で解けるということも知られている. 本稿では, この特殊な場合に焦点を当て, これまでに行われた研究を概観するとともに, いくつかの話題を提供する.