এই সমস্যায়, আমাদেরকে একটি অ্যারে 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
