C++で最大M個の商品を販売して利益を最大化するアルゴリズム

この記事では、最大「M」個の商品を販売したときに得られる利益の最大値を求める問題について解説します。

商品の総数は「N」個で、各商品の仕入れ値（原価）と販売価格は、それぞれリスト CP[] と SP[] に格納されています。

入力例と出力例

例1

N=6, M=4
CP[]={1,9,5,8,2,11}
SP[]={1,15,10,16,5,20}

出力：

28

説明： 各商品を販売したときに得られる利益は、順に 0、6、5、8、3、9 となります。4つの商品だけを販売して利益を最大化するには、最も利益の高い商品、すなわち2番目・3番目・4番目・6番目の商品を選ぶ必要があります。

最大利益 = 6 + 5 + 8 + 9 = 28

例2

N=3, M=2
CP[]={10,20,30}
SP[]={19,22,38}

出力：

17

アルゴリズムのアプローチ

• 各商品から得られる利益を格納するため、int型でサイズ「N」の配列 Profit[] を作成します。

• 最終的な最大利益を格納するため、int型の変数 Total を作成します。

• i=0 から i<N までループ処理を行います。

• ループ内で Profit[i] = Sp[i] − Cp[i] を設定し、各商品の利益を計算します。

• sort(Profit, Profit + N, greater<int>()) 関数を呼び出し、Profit[] 配列を降順に並べ替えます。

• 再び i=0 から i<M までループ処理を行います。

• ループ内で if(Profit[i]>0) の条件文により値が正かどうかを確認し、正の場合は total += Profit[i]; を実行します。

• total を返します。

この手法は貪欲法（グリーディ法）の一種です。利益がマイナスになる商品を販売しても損失が増えるだけで意味がないため、降順に並べ替えた利益の中から正の値を持つ上位M個だけを選んで合計することで、効率的に最大利益を求められます。時間計算量は O(N log N) となり、これはソート処理が支配的です。

C++実装例

#include <bits/stdc++.h>
using namespace std;
// 利益を求める関数
int MaxProfit(int N, int M, int Cp[], int Sp[]){
    int Profit[N];
    int total = 0;
    // 各商品からの利益を計算
    for (int i = 0; i < N; i++)
        Profit[i] = Sp[i] - Cp[i];
    // 利益配列を降順に並べ替え
    sort(Profit, Profit + N, greater<int>());
    // 最も利益の高いM個の合計を計算
    for (int i = 0; i < M; i++){
        if (Profit[i] > 0)
            total += Profit[i];
        else
            break;
    }
    return total;
}
// メイン関数
int main(){
    int MP;
    int N=6,M=4;
    int CP[] = { 1, 9, 5, 8, 2, 11 };
    int SP[] = { 1, 15, 10, 16, 5, 20 };
    MP = MaxProfit(N, M, CP, SP);
    cout<<"Maximum Profit:"<<MP;
    return 0;
}

出力結果

上記のコードを実行すると、以下の出力が得られます。

Maximum Profit: 28

まとめ

本記事では、販売できる商品数に上限がある状況下で利益を最大化する問題を取り上げました。各商品の利益を計算し、降順ソートによって利益の高い商品から順に選択するというシンプルな貪欲法のアプローチにより、O(N log N) の計算量で解けることを確認しました。類似の最適化問題にも応用できる考え方なので、ぜひ理解を深めてください。