C++で解く！ハンバーガーとチキンバーガー販売の最大利益を求めるアルゴリズム

問題概要

5つの整数 b、p、f、h、c が与えられます。レストランでは2種類のバーガーを販売しており、それぞれ次の材料が必要です。

• ハンバーガー： パン2個＋ビーフパティ1枚 → h ルピーで販売
• チキンバーガー： パン2個＋チキンカツ1枚 → c ルピーで販売

現在の在庫は、パンが b 個、ビーフパティが p 枚、チキンカツが f 枚です。この条件下で、売上の最大値（最大利益）を求めます。

例えば、b = 7、p = 5、f = 2、h = 10、c = 12 の場合、出力は 34 になります。これは、ハンバーガー1個とチキンバーガー2個を作ると、収入が 1×10 ＋ 2×12 ＝ 34 ルピーになるためです。

解法のアプローチ：貪欲法

この問題は貪欲法（グリーディ法）で効率的に解けます。ポイントは「より高い価格で売れるバーガーを優先的に作る」ことです。具体的な手順は以下の通りです。

res := 0
b := b / 2
if h < c, then:
    swap(p, f)
    swap(h, c)
res := res + h * min(b, p) + c * min(max(b - p, 0), f)
return res

手順のポイント

• パンの数を半分にする： バーガー1個につきパン2個が必要なため、実際に作れるバーガーの上限は b ÷ 2 個になります。
• 高額な方を常に先に処理： もし h < c なら、パティとカツ、価格の変数を入れ替えます。これにより、以降の計算では必ずハンバーガー（h）の方が高価になります。
• 利益の計算： まず高い方のバーガーを min(b, p) 個作り、その後、余ったパン max(b − p, 0) を使って、低い方のバーガーを min(max(b − p, 0), f) 個だけ追加で作ります。

C++での実装例

それでは、上記のロジックをC++で実装してみましょう。

#include <bits/stdc++.h>
using namespace std;

int solve(int b, int p, int f, int h, int c) {
    int res = 0;
    b /= 2;                 // 作れるバーガーの最大数
    if (h < c) {            // チキンバーガーの方が高い場合は入れ替え
        swap(p, f);
        swap(h, c);
    }
    // 高い方を優先的に作り、残りのパンでもう一方を作る
    res += h * min(b, p) + c * min(max(b - p, 0), f);
    return res;
}

int main() {
    int b = 7;
    int p = 5;
    int f = 2;
    int h = 10;
    int c = 12;
    cout << solve(b, p, f, h, c) << endl;
}

入力

7, 5, 2, 10, 12

出力

34

計算量について

このアルゴリズムは比較と四則演算のみで構成されているため、時間計算量は O(1)、空間計算量も O(1) となります。入力サイズに依存せず一定時間で答えが求まるため、非常に効率的な解法です。