現場で使えるアルゴリズム入門～動的計画法で計算効率を大幅UP！～

2025年10月28日

現場で使えるアルゴリズム入門～動的計画法で計算効率を大幅UP！～

はじめまして、7月入社のJanです。

突然ですが、ITエンジニアの皆さんに質問です。
日々の業務の中でこんな場面に遭遇したことはないでしょうか？

例えば：

数千件のデータ処理に時間がかかってしまう
データの重複チェックがボトルネックになっている
条件分岐が多すぎてメンテナンスが大変になってきた

こうした課題に対して、「とりあえず動いているからOK」としてしまうと、後々の不具合や手戻りにつながるリスクがあります。
そんなときに役立つのが、アルゴリズム的な視点です。

アルゴリズムとは、問題を効率よく解くための「手順」や「考え方」のことです。
データの処理順序を工夫したり無駄な操作を減らしたりする方法を身につけることで、より効率的でミスの少ないコードを書けるようになります。

本記事では、そんな日々の業務の中で活用できる（かもしれない）アルゴリズムのひとつ、「動的計画法」について解説します。

専門的な知識は必要ありませんので、ぜひ気軽に読んでみてください！

侮れない計算効率の問題

プログラムを書いた経験のある人なら、一度は処理速度に悩まされたことがあるのではないでしょうか。
大量のデータを扱ったり、複雑な処理を繰り返したりしていると、どうしても処理時間が長くなってしまいますよね。

そこで今回は、計算効率の問題に焦点を当て、実践的な例題を通じてその解決方法を考えてみたいと思います。
お時間があれば、ぜひ挑戦してみてください！

例題：仕入れ管理システム開発

あなたは、小売業向けの仕入れ管理システムの開発を担当しています。

取り扱う商品にはそれぞれ仕入れコストと、その商品を仕入れた場合に期待される利益が設定されており、予算内で各商品を何個でも仕入れることができます。

利益が最大となるように仕入れを行った場合の利益と、各商品の仕入れ数を出力してください。答えが複数通りある場合は、どれか1つを出力すれば正解とします。

入力形式

N B
c_1 p_1
c_2 p_2
...
c_N p_N

・一行目に商品数を表す正の整数Nと予算を表す正の整数 B が半角スペース区切りで与えられます。
・続くN行には商品の仕入れコストを表す正の整数 c_i (1≦i≦N) と利益を表す正の整数 p_i (1≦i≦N) が半角スペース区切りで与えられます。

出力形式

・利益が最大となるように仕入れを行った場合の利益の合計を出力してください。
・続くN行には i (1≦i≦N) 番目の商品の仕入れ数を出力してください。

入力例

出力例

シンプルだけど遅い全探索

この問題に対する最もシンプルなアプローチは、すべての商品の組み合わせを試してみることです。

以下に、pythonの実装例をご紹介します。

# 予算に対する最大利益と各商品の仕入れ数を求める関数
def get_best_purchase(N,budget,i, costs, profits):
    # すべての商品を検討した場合、合計利益0と空の購入個数を返す
    if i == N:
        return 0, [0] * N

    # 商品iを含めた最大利益と購入個数を初期化
    max_profit, counts = 0, [0] * N

    # 商品iを0個から予算内で可能な最大数まで試す
    count = 0

    while count * costs[i] <= budget:
        # 残り予算と次の商品で再帰
        profit_next, counts_next = get_best_purchase(N, budget - count * costs[i], i + 1, costs, profits)
        total_profit = profit_next + count * profits[i]

        # より利益が大きければ更新
        if total_profit > max_profit:
            max_profit = total_profit
            counts_next[i] = count
            counts = counts_next

        count += 1

    return max_profit, counts

# 標準入力を受け取る
N, B = map(int, input().split())
costs, profits = zip(*(map(int, input().split()) for i in range(N)))

# 結果を出力
max_profit, counts = get_best_purchase(N, B, 0, costs, profits)
print(max_profit)
for i in counts:
    print(i)

上記の全探索による解法は、問題なく入力例のケースを解くことができます。

一見するとこれで良さそうですが、このコードには致命的な欠陥があります。それは、商品数や予算が増えると計算量が爆発的に増加し、処理時間が許容できないほど長くなってしまうことです。
(こんなシステムを納品したらクレームが来てしまいます…)

商品数が増えても問題なく動くように計算を効率化する必要がありますが、そこで登場するのが今回ご紹介するアルゴリズム「動的計画法(Dynamic Programming, DP)」です！

動的計画法で計算を効率化しよう！

動的計画法って何？

「動的計画法」なんて言われても、ピンとこない方も多いかもしれませんが、簡単に言うと「計算を効率よくするために、計算した結果を覚えておく方法」です。

例えば、あなたが「A + B」という計算をした後に、「A + B + C」を計算するときのことを考えてみてください。
「A + B」の結果がすでにわかっているなら、再度計算する必要はありませんよね？事前に計算した「A + B」に「C」を加えるだけで済みます。
こういった「過去に計算した結果を覚えておいて、無駄に同じ計算を繰り返さない」というのが、動的計画法の基本的な考え方です。

実際に使ってみよう！

さて、先ほどの例題を、動的計画法を使って解いてみましょう！

具体的な流れは以下の通りです。

１．DPテーブルの準備

最初に、動的計画法を使うためにはDPテーブルを準備します。
ここでいう「テーブル」とは、予算ごとに得られる最大利益を記録しておく配列のことです。

今回は dp[B + 1] という配列をつくり、予算 budget のときに得られる最大利益を dp[budget] に格納していきます。

また、各商品の仕入れ数をカウントするため、 counts[B + 1][N] という配列もつくっておきます。

２．最大利益、仕入れ数を更新する

i番目の商品(商品i)の仕入れコスト(cost_i)と利益(profit_i)を使って、以下のように予算 budget の時に得られる最大利益を計算します。

商品iを選ばない場合は、現在の予算budgetの時に得られる最大利益はそのまま dp[budget] です。
商品Aを選んだ場合は、予算 budget からcost_A を引いた金額で、残りの予算に対する最大利益に、Aの利益を加算します。つまり、 dp[budget - cost_i] + profit_i です。
これらを比較し商品Aを選んだ場合の方が最大利益が大きければ、 dp[budget] の値を更新します。また、その場合の仕入れ数も counts[B] に反映させます。

この処理を予算 cost_i から B まですべての商品で行い、最後に dp[B] と counts[B] に格納されている値が答えになります。

以下に、pythonの実装例をご紹介します。

# 予算に対する最大利益と各商品の仕入れ数を求める関数
def get_best_purchase(N, B,costs,profits):
    # dp[i] は予算iで得られる最大利益を保持
    dp = [0] * (B + 1)
    # counts[i]は予算iで最大利益を得られる場合の各商品の仕入れ数を保持
    counts = [[0 for j in range(N)] for i in range(B + 1)]

    for i in range(N):
        cost_i = costs[i]
        profit_i = profits[i]

        for budget in range(cost_i, B + 1):
            # 商品を選んだ場合の利益が最大利益を超えれば更新
            if dp[budget - cost_i] + profit_i > dp[budget]:
                dp[budget] = dp[budget - cost_i] + profit_i
                counts[budget] = counts[budget - cost_i][:]
                counts[budget][i] += 1

    # 予算Bの場合の最大利益と各商品の仕入れ数
    return dp[B],counts[B]

# 標準入力を受け取る
N, B = map(int, input().split())
costs, profits = zip(*(map(int, input().split()) for i in range(N)))

# 結果を出力
max_profit,counts = get_best_purchase(N, B, costs, profits)

print(max_profit)
for i in counts:
    print(i)

全探索と動的計画法の計算量比較

商品数ごとに、全探索と動的計画法で必要な計算量（ステップ数）を比較すると、次のようになります。

全探索では、各商品について予算内で可能な仕入れ数（平均 M 通りとする）をすべて試すため、処理回数は M^N となります。つまり、商品数 (N) が増えると計算量は指数関数的に増加し、非常に大きな処理時間が必要になります。
一方、動的計画法では、商品ごとに予算1円単位で最適解を更新するだけなので、処理回数は N × B に抑えられます。

計算量の比較表

商品数（N）	全探索（概算処理回数）	動的計画法（処理回数）	差分（倍率）
5	約 312 万回	500 回	約 6,200 倍
10	約 976 億回	1,000 回	約 9,760 万倍
20	約 954 兆回	2,000 回	約 4,770 億倍
30	約 931 京回	3,000 回	約 3,100 兆倍

💡 予算を100としたとき、各商品について平均5通りの仕入れ数（0〜4個）を試すケース

こうして数字で見比べてみると、アルゴリズムによる差がどれほど大きいかが一目瞭然ですね！

まとめ

本記事では「動的計画法」というアルゴリズムを紹介しましたが、計算効率を改善する方法は他にもたくさんあります！

開発現場で計算効率に関する問題に直面した際、アルゴリズムの引き出しが豊富だと、その場に最適な解決策を素早く見つけることができるので非常に便利です。

アルゴリズムの知識は、ITエンジニアとして大きな武器になりますので、ぜひ積極的に学んでいきましょう。

次回は別のアルゴリズムについても取り上げる予定ですので、ぜひお楽しみに！

TechBlog
株式会社i-Vinciの技術ブログ