部分和問題を動的計画法で解く - Qiita

概要 これは Money Forward Engineering Advent Calendar 2021 3 日目の記事です 🎄 運用しているとある Rails アプリケーションのある機能でリクエストがタイムアウトしてしまう問題が生じたのが発端です。ある n 個の整数の集合 $\{a_1, a_2, ..., a_n\}$ から、和が与えられた sum に等しくなるように部分集合を選ぶ問題を解く処理があります。この問題を 部分和問題 と呼びます。例えば集合が $\{3, 34, 4, 12, 5, 2\}$ で sum = 20 の場合、和が 20 となる部分集合は $\{3, 12, 5\}$です。 今回 n の数がある程度大きい場合に、Rails アプリケーション内の処理に含まれる部分和問題を数分では解くことができず、結果 HTTP リクエストのタイムアウトが発生してしまいました。