C++プログラムでの最大重量差

この問題では、配列arr []と数値Mが与えられます。私たちのタスクは、C++での最大重み差を計算するプログラムを作成することです。

問題の説明

We will find M elements from the array such that the absolute difference
between the sum and the sum of the rest elements is maximum.

問題を理解するために例を見てみましょう

入力

arr[] = {3, 1, 6, 9, 4} M = 3

出力

15

説明

4,6,9を検討します。合計は19です。残りの数の合計との絶対差は

|19 − 4| = 15

ソリューションアプローチ

この問題の簡単な解決策は、配列のすべてのサブシーケンスを検索し、サブ配列の合計要素を検索し、残りを検索することです。そして、最大の差を返します。

サブシーケンスにm個の最大要素またはm個の最小要素を考慮すると、最大の重みの差、つまり要素の合計と残りの要素の差が最大になるという事実を使用することで、より効率的な解決策が見つかります。

したがって、最大の要素と残りの配列のサブシーケンス、またはm個の最小の要素と残りの配列のサブシーケンスの最大合計差を確認します。

そして、両方の最大値を返します。

アルゴリズム

初期化 −

maxSum , maxSumDiff, minSumDiff

ステップ1 −

sort the array in descending order.

ステップ2 −

Loop for i −> 0 to n

ステップ2.1 −

if (i < m) −> maxSumDiff += arr[i]

ステップ2.2 −

else −> maxSumDiff −= arr[i]

ステップ2 −

Loop for i −> n to 0

ステップ2.1 −

if (i > m) −> minSumDiff += arr[i]

ステップ2.2 −

else −> minSumDiff −= arr[i]

ステップ3 −

if maxSumDiff > minSumDiff −> maxSum = maxSumDiff.

ステップ4 −

if maxSumDiff < minSumDiff −> maxSum = minSumDiff.

ステップ5 −

return maxSum.

例

ソリューションの動作を説明するプログラム

#include <bits/stdc++.h>
using namespace std;
int maxWeightDifference(int arr[], int N, int M){
   int maxabsDiff = −1000;
   sort(arr, arr + N);
   int sumMin = 0, sumMax = 0, arrSum = 0;
   for(int i = 0; i < N; i++){
      arrSum += arr[i];
      if(i < M)
         sumMin += arr[i];
      if(i >= (N−M))
         sumMax += arr[i];
   }
   maxabsDiff = max(abs(sumMax − (arrSum − sumMax)), abs(sumMin −
   (arrSum − sumMin)));
   return maxabsDiff;
}
int main(){
   int arr[] = {3, 1, 6, 9, 4} ;
   int M = 3;
   int N = sizeof(arr)/sizeof(arr[0]);
   cout<<"The maximum weight difference is "<<maxWeightDifference(arr,N, M);
   return 0;
}

出力

The maximum weight difference is 15