LCM Knapsack

2 secs 1024 MB

この問題は動的計画法により $O(NW \ \mathrm{log} W)$ で解くことができます。

ナップサック問題という有名問題がありますが、その品物の総重量の定義を最小公倍数に変更したのが本問です。よって、基本的にはナップサック問題と同様にして動的計画法により解くことができます。以下では、相違点のみ言及します。

最小公倍数には結合法則が成り立つため、順序を気にせず累積計算できます（加法と最小公倍数は異なりますが、結合的である点では同じです）。
- $\mathrm{lcm}(a,\mathrm{lcm}(b,c)) = \mathrm{lcm}(\mathrm{lcm}(a,b),c)$
最小公倍数 $\mathrm{lcm}(a,b)$ $lcm (a, b)$ はユークリッドの互除法により $O(\mathrm{log}(\mathrm{min}(a, b)))$ $O (log (min (a, b)))$ で計算可能です。
- $\mathrm{lcm}(a,b) = ab / \mathrm{gcd}(a,b)$
全体計算量は動的計画法パートの $O(NW)$ と合わせて $O(NW \ \mathrm{log} W)$ です。
実装上の注意として、「 $i$ $i$ 番目の品物を選ぶ」遷移をする際、最小公倍数を計算して遷移元と遷移先を対応付ける都合上、いわゆる「配る DP」によって実装するのがよいです。「貰う DP」にすると遷移元が複数存在する可能性があるため、計算量が少し悪化する上に実装も大変になります。下記に具体例を示します。
- （配る DP）現在の最小公倍数が $15$ だとして $w_i = 6$ を選ぶと、遷移先の最小公倍数は $\mathrm{lcm}(15,6) = 30$ と一意に定まります。
- （貰う DP） $w_i = 6$ を選んだとき最小公倍数が $30$ になるような遷移元の最小公倍数を考えると、 $\{ 5, 10, 15, 30 \}$ の $4$ つあり複数存在します。

解説