実生活に沿った例で考える動的計画法(001)

はじめに

競技プログラミングもやりたいけれど、目的はプログラミングスキルの上昇とアルゴリズムの習得および問題解法のスキルアップでした。

なので、与えられた問題を解くだけでなく実生活にあったパターンに落とし込んでいかねばと考える昨今。

構想はあったものの中々手を出せずにいたので、今年からやってみようかと思います。

色々試行錯誤なので、投稿しながらブラッシュアップしていきたいと思います。

投資戦略問題(001)

動的計画法のオーソドックスな問題である投資戦略問題から考えてみます。

あなたは投資家であり、5つの異なる企業（A社、B社、C社、D社、E社）に投資する機会がある。
各企業への投資には最小投資額があり、それぞれの投資に対して期待利益が設定されている。
あなたの総投資可能額は1000万円である。
各企業への投資額と期待利益は以下の通りである：

A社: 最小投資額200万円、期待利益7.5%
B社: 最小投資額150万円、期待利益6.0%
C社: 最小投資額300万円、期待利益10.0%
D社: 最小投資額250万円、期待利益9.0%
E社: 最小投資額100万円、期待利益5.0%

総投資可能額1000万円を使って、期待利益の合計を最大化するための最適な投資戦略を求めるプログラムを作成せよ。
ただし、各企業への投資は最小投資額の整数倍でのみ可能とする。

解答サンプル(001)

dp.py

def dp_sample(total_amount, companies):
    # 動的計画法のテーブルを初期化
    dp = [0] * (total_amount + 1)

    # 各企業について投資を検討
    for company, (min_investment, profit_rate) in companies.items():
        for amount in range(total_amount, min_investment - 1, -1):
            # 現在の投資額から、この企業に投資可能な最大回数を計算
            max_investments = amount // min_investment
            for i in range(1, max_investments + 1):
                investment = i * min_investment
                profit = investment * profit_rate
                dp[amount] = max(dp[amount], dp[amount - investment] + profit)

    # 最適な投資戦略を復元
    amount = total_amount
    strategy = {}
    for company, (min_investment, _) in reversed(companies.items()):
        while amount >= min_investment and dp[amount] == dp[amount - min_investment] + min_investment * companies[company][1]:
            strategy[company] = strategy.get(company, 0) + min_investment
            amount -= min_investment

    return dp[total_amount], strategy

if __name__ == "__main__":
    # 総投資可能額（万円）
    total_amount = 1000

    # 企業ごとの最小投資額と期待利益率
    companies = {
        'A': (200, 0.075),
        'B': (150, 0.06),
        'C': (300, 0.10),
        'D': (250, 0.09),
        'E': (100, 0.05)
    }

    # 最適な投資戦略を計算
    max_profit, best_strategy = dp_sample(total_amount, companies)

    # 結果を出力
    print(f"最大期待利益: {max_profit:.2f}万円")
    print("最適な投資戦略:")
    for company, amount in best_strategy.items():
        print(f"{company}社: {amount}万円")
    print(f"総投資額: {sum(best_strategy.values())}万円")

トレース

DP問題の典型例で、とりあえず350万で考えてみる。

A社B社の2社の場合

150万・・・B社→利益9万
200万・・・A社→利益15万
350万・・・A社→利益15万, B社→利益9万: 計24万

A社B社C社の3社の場合

150万・・・B社→利益9万
200万・・・A社→利益15万
300万・・・C社→利益30万
350万・・・A社→利益15万, B社→利益9万: 計24万と利益30万の大きい方 → C社のみの方が良い

A社B社C社D社の4社の場合

150万・・・B社→利益9万
200万・・・A社→利益15万
250万・・・D社→利益22.5万
300万・・・C社→利益30万
350万・・・C社→利益30万☆(C社を購入することは前のケースで確定済み)

A社B社C社D社E社の5社の場合

100万・・・E社→利益5万
150万・・・B社→利益9万
200万・・・A社→利益15万（E社×2だと10万）
250万・・・D社→利益22.5万（E社＋B社だと14万）
300万・・・C社→利益30万（E社＋A社だと20万）
350万・・・C社→利益30万（E社×3だと15万、E社＋D社だと27.5万）

これを1000万のケースで考えれば良い。また、プログラムなので条件が同じであれば他の変数で試してもよい。

この例ではDP更新が少なかったけれど、F社G社H社・・・など増えてきても、一つ前までに決めた値を使いまわすことが可能。

本コードはかなり効率悪いけれど、投資の問題であれば1万円単位で考えるのが現実的だし、10億円くらいであれば、このコードで十分な気がしてます。

1円単位を気にするのであれば、投資じゃなくてギャンブル問題になるし、プログラミング学習であれば、投資問題の方が良かったかも…

投資戦略問題(002)→total_amountを大きくするとバグ正常に計算できないDP処理にバグあり

ある投資家が複数の企業に投資を行う計画を立てている。
各企業には最小投資額と最大投資額が設定されており、投資額に応じて異なる期待利益率が適用される。
総投資可能額が決まっている中で、最大の期待利益を得るための最適な投資戦略を求める問題である。

具体的には、以下の条件が与えられる：
1. 総投資可能額（例：1000万円）
2. 各企業の投資条件：
   - 企業名
   - 最小投資額
   - 最大投資額
   - 投資額別の期待利益率（段階的に変化）

目標は、総投資可能額の範囲内で、各企業への投資額を決定し、全体の期待利益を最大化することである。
ただし、各企業への投資は、その企業の最小投資額と最大投資額の範囲内でなければならない。

解答サンプル(002)

dp.py

def dp_sample(total_amount, companies):
    # 動的計画法のテーブルを初期化。インデックスは投資額、値は最大利益
    dp = [0] * (total_amount + 1)

    # 各企業について投資を検討
    for company, info in companies.items():
        # 企業ごとの最小投資額、最大投資額、利益率のリストを取得
        min_inv, max_inv, profit_rates = info
        # 総投資額から最小投資額まで逆順に走査（重複計算を避けるため）
        for amount in range(total_amount, min_inv - 1, -1):
            # 現在の企業への投資額を最小から最大まで検討
            for inv in range(min_inv, min(amount + 1, max_inv + 1)):
                # 投資額に応じた利益率を決定（閾値以下の最初の利益率を選択）
                rate = next(rate for threshold, rate in profit_rates if inv <= threshold)
                # 現在の投資による利益を計算
                profit = inv * rate
                # 最大利益を更新（現在の投資を行う場合と行わない場合を比較）
                dp[amount] = max(dp[amount], dp[amount - inv] + profit)

    # 最適な投資戦略を復元
    amount = total_amount
    strategy = {}
    # 企業を逆順に走査（最後に投資した企業から順に決定）
    for company, (min_inv, max_inv, profit_rates) in reversed(companies.items()):
        # 現在の企業への投資額を最小から最大まで検討
        for inv in range(min_inv, min(amount + 1, max_inv + 1)):
            # 投資額に応じた利益率を決定
            rate = next(rate for threshold, rate in profit_rates if inv <= threshold)
            # この投資が最適解の一部であるかチェック
            if amount >= inv and dp[amount] == dp[amount - inv] + inv * rate:
                # 最適解の一部である場合、戦略に追加
                strategy[company] = inv
                # 残りの投資可能額を更新
                amount -= inv
                break

    # 最大利益と最適投資戦略を返す
    return dp[total_amount], strategy

if __name__ == "__main__":
    # 総投資可能額（万円）
    total_amount = 1000

    # 企業ごとの投資条件（最小投資額、最大投資額、投資額別期待利益率）
    companies = {
        'A': (100, 400, [(200, 0.030), (300, 0.045), (400, 0.054)]),
        'B': (200, 500, [(300, 0.036), (400, 0.048), (500, 0.060)]),
        'C': (300, 600, [(400, 0.042), (500, 0.054), (600, 0.066)])
    }

    # 最適な投資戦略を計算
    max_profit, best_strategy = dp_sample(total_amount, companies)

    # 結果を出力
    print(f"最大期待利益: {max_profit:.2f}万円")
    print("最適な投資戦略:")
    for company, amount in best_strategy.items():
        print(f"{company}社: {amount}万円")
    print(f"総投資額: {sum(best_strategy.values())}万円")

おわりに

個人的に、高校生の教材とかも、ナップサック問題でなく、こういうお金の問題で教えればいいと思ってるのですよね。

変に「金融教育」だなんてやらずに、数学でもプログラミングでも実生活に紐づけて教えれば興味を持つだろうし、題材なんて既存教育内でも、そこかしこに転がってると思ってるんだけどなぁ。