Trong bài toán này, chúng ta được cung cấp một mảng arr [] và một số M. Nhiệm vụ của chúng ta là tạo một chương trình để tính Chênh lệch Trọng số Tối đa trong C ++.
Mô tả sự 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.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
arr[] = {3, 1, 6, 9, 4} M = 3 Đầu ra
15
Giải thích
Chúng ta sẽ xem xét 4,6,9. Tổng là 19. Chênh lệch tuyệt đối với các số còn lại của sumof là
|19 − 4| = 15
Phương pháp tiếp cận giải pháp
Một giải pháp đơn giản cho vấn đề là tìm tất cả các dãy con của mảng, tìm tổng các phần tử của mảng con và phần còn lại. Và trả lại số tiền chênh lệch tối đa.
Một giải pháp hiệu quả hơn được tìm thấy bằng cách sử dụng thực tế là chênh lệch trọng số tối đa, tức là hiệu số của tổng các phần tử và phần còn lại là lớn nhất nếu chúng ta xem xét m phần tử tối đa hoặc m phần tử tối thiểu theo thứ tự.
Vì vậy, chúng tôi sẽ kiểm tra sự khác biệt tổng lớn nhất cho dãy con của phần tử lớn nhất và mảng còn lại hoặc dãy con của m phần tử nhỏ nhất và mảngrest.
Và trả về giá trị tối đa của cả hai.
Thuật toán
Khởi tạo -
maxSum , maxSumDiff, minSumDiff
Bước 1 -
sort the array in descending order.
Bước 2 -
Loop for i −> 0 to n
Bước 2.1 -
if (i < m) −> maxSumDiff += arr[i]
Bước 2.2 -
else −> maxSumDiff −= arr[i]
Bước 2 -
Loop for i −> n to 0
Bước 2.1 -
if (i > m) −> minSumDiff += arr[i]
Bước 2.2 -
else −> minSumDiff −= arr[i]
Bước 3 -
if maxSumDiff > minSumDiff −> maxSum = maxSumDiff.
Bước 4 -
if maxSumDiff < minSumDiff −> maxSum = minSumDiff.
Bước 5 -
return maxSum.
Ví dụ
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
#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;
} Đầu ra
The maximum weight difference is 15