品物の数が n、ナップサックの容量が整数 W の0-1ナップサック問題を、「最初の i 個の品物から選び、重さの合計が w 以下のときの価値の最大値」を表に記録する動的計画法で解く。このときの時間計算量はどれか。

解説

正解は「$O(nW)$」です。表 T[i][w] の各欄は、「品物 i を入れない場合の T[i−1][w]」と「入れる場合の T[i−1][w − 重さ] + 価値」の大きい方で決まるので、定数時間で求まります。欄の数は約 $n\times W$ 個なので、全体で $O(nW)$ です。容量 W の値に比例するため、W が非常に大きいと遅くなります。「$O(2^n)$」は、各品物を入れるか入れないかの全組合せを列挙する場合の計算量です。「$O(n\log n)$」は、品物を単価順に整列して詰める貪欲法の計算量で、品物を分割できるナップサック問題の解法です。「$O(n!)$」は品物の並べ方をすべて調べる場合で、組合せの問題には不要です。