整数ナップサック問題が多項式時間で解ける特殊な場合を定める条件について

• 資料種別: 規格・テクニカルリポート類
• タイトル: 整数ナップサック問題が多項式時間で解ける特殊な場合を定める条件について
• 著者・編者: 飯田, 浩志
• 著者標目: 飯田, 浩志
• 出版事項: 小樽商科大学ビジネス創造センター
• 出版年月日等: 2005-07
• 出版年（W3CDTF）: 2005-07
• タイトル（掲載誌）: Discussion paper series
• 巻号年月日等（掲載誌）: 101
• 掲載巻: 101
• 掲載ページ: 1-7
• 本文の言語コード: jpn
• 件名標目: 数学; 組合せ最適化; ナップサック問題; 貪欲法; 多項式アルゴリズム
• NDC: 410
• 対象利用者: 一般
• 一般注記: 出版タイプ： VoR
• オンライン閲覧公開範囲: インターネット公開
• 連携機関・データベース: 国立情報学研究所 : 学術機関リポジトリデータベース（IRDB）（機関リポジトリ）; https://irdb.nii.ac.jp
• 提供元機関・データベース: 小樽商科大学 : 小樽商科大学学術成果コレクション

• 要約等: 整数ナップサック問題は, よく知られた0?1 ナップサック問題の数ある拡張の一つである.0?1 ナップサック問題の拡張ゆえに, 整数ナップサック問題も容易には解けない問題であり, 分枝限定法・動的計画法等の一般的な枠組みを用いて解かざるを得ない. しかしその一方で, ある特殊な場合には多項式時間で解...