ในปัญหานี้ เราได้รับอาร์เรย์ 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
