資料結構
網路
關係型資料庫管理系統(RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究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個最大元素的子序列和其餘陣列，或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
更新於：2020年12月9日
196 次瀏覽
廣告