C++で2つの配列からX個とY個の要素を選び、合計を最大化する方法

サイズNの2つの配列が与えられたとき、1つ目の配列からX個、2つ目の配列からY個の要素を選択して、その合計を最大化することが課題です。

具体的な例を使って、何をすべきか見ていきましょう。

入力例1

arr1 = {1,2,3,4,5} ; X=2
arr2 = {1,3,5,2,7}; Y=3

出力例1

最大合計値 : 24

解説： arr1から2つ、arr2から3つの数値を選びます。arr1の大きい方から2つは「4, 5」、arr2の大きい方から3つは「3, 5, 7」です。これら5つの要素の合計は24となり、これが条件を満たす最大値になります。

入力例2

arr1 = {10,13,16,14}; X=1
arr2 = {4,1,2,1}; Y=2

出力例2

最大合計値 : 22

解説： arr1から1つ、arr2から2つの数値を選びます。arr1の最大値は「16」、arr2の大きい方から2つは「4, 2」です。これら3つの要素の合計は22となり、これが最大値となります。

プログラムで使用するアプローチ

• 入力として配列arr1[]とarr2[]、およびXとYの値を受け取ります。

• 両方の配列を昇順にソートします。

• ソート後は末尾の要素が最も大きくなるため、arr1からは末尾のX個、arr2からは末尾のY個を取り出します。

• 手順3で選んだ要素の合計を返します。それが最大の合計値となるためです。

• 注意：sort(arr[], int)はソート済みの配列を返すものと仮定しています。

実装例

#include <iostream>
using namespace std;
int max_sum(int arr1[],int arr2[], int length,int X,int Y){
    // 配列をソートする
    sort(arr1,length);
    sort(arr2,length);
    int sum=0;
    int i;
    // arr1の末尾X個とarr2の末尾Y個を加算する
    for(i=0;i<X;i++){
        sum+=arr1[length-i-1];
    }
    for(i=0;i<Y;i++){
        sum+=arr2[length-i-1];
    }
    return(sum);
}
// ドライバープログラム
int main(){
    int arr1[]={1,1,1,3,7};
    int arr2[]={1,1,2,3,5};
    int x=3,y=2;
    printf( "1番目と2番目の配列からX個とY個の要素を選んだ場合の最大化された合計は %d",max_sum(arr1,arr2,5,x,y));
    return 0;
}

出力結果

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

1番目と2番目の配列からX個とY個の要素を選んだ場合の最大化された合計は 19

このアルゴリズムの計算量は、ソートにO(N log N)、要素の選択と合計にO(X + Y)かかるため、全体としてO(N log N)となります。貪欲法（グリーディ法）に基づくシンプルな手法で、各配列から最大の要素を優先的に選ぶことで確実に最大の合計を得られます。