動的計画法を用いた多次元ナップサック問題の変数縮小法

(Misato Yamashita) Graduate School of Science and Engineering, National Defense Academy (Seiji Ka...概要を表示 (Misato Yamashita) Graduate School of Science and Engineering, National Defense Academy (Seiji Kataoka) Department of Computer Science, National Defense Academy 1 ($KP$ : Knapsack Problem) $KP$ (MDKP: Multidimensional Knapsack Problem) 0-1 Martello-Toth[4] Kellerer-Pferschy-Pisinger[3] 1 2 $KP$ ($DP$ :Dynamic Programming) 2 ( ) $m$ MDKP (MDKP) $\max$ $\sum_{j=1}^{n}p_{j}x_{j}$ (1) s.t. $\sum_{j=1}