Maximaler Gewichtsunterschied
Sie erhalten ein Array W[1], W[2], …, W[N]. Wählen Sie darunter K Zahlen so aus, dass die absolute Differenz zwischen der Summe der gewählten Zahlen und der Summe der verbleibenden Zahlen möglichst groß ist.
Beispiele:
Input : arr[] = [8, 4, 5, 2, 10]
k = 2
Output: 17
Input : arr[] = [1, 1, 1, 1, 1, 1, 1, 1]
k = 3
Output: 2
Es gibt zwei Möglichkeiten, die gewünschte Antwort zu erhalten. Diese beiden sind: Wähle k größte Zahlen oder Wähle k kleinste Zahlen. Wählen Sie die am besten geeignete Option, die gemäß den angegebenen Werten passt. Dies liegt daran, dass es einige Fälle gibt, in denen die Summe der kleinsten k Zahlen größer als der Rest des Arrays sein kann, und es gibt einige Fälle, in denen die Summe der größten k Zahlen größer als der Rest der Summe der Zahlen sein kann.
Sich nähern :
- Sortieren Sie das angegebene Array.
- Holen Sie sich die Summe aller Zahlen des Arrays und speichern Sie sie in Summe
- Holen Sie sich die Summe der ersten k Zahlen des Arrays und speichern Sie sie in sum1
- Holen Sie sich die Summe der letzten k Zahlen des Arrays und speichern Sie sie in sum2
- Geben Sie das Ergebnis aus: max(abs(S1-(S-S1)), abs(S2-(S-S2)))
C++
// C++ Program to find maximum weight
// difference
#include <iostream>
#include <algorithm>
using namespace std;
// return the max value of two numbers
int solve(int array[], int n, int k)
{
// sort the given array
sort(array, array + n);
// Initializing the value to 0
int sum = 0, sum1 = 0, sum2 = 0;
// Getting the sum of the array
for (int i = 0; i < n; i++) {
sum += array[i];
}
// Getting the sum of smallest k elements
for (int i = 0; i < k; i++) {
sum1 += array[i];
}
sort(array, array+n, greater<int>());
// Getting the sum of k largest elements
for (int i = 0; i < k; i++) {
sum2 += array[i];
}
// Returning the maximum possible difference.
return max(abs(sum1 - (sum - sum1)), abs(sum2 -
(sum - sum2)));
}
// Driver function
int main()
{
int k = 2;
int array[] = { 8, 4, 5, 2, 10 };
// calculate the numbers of elements in the array
int n = sizeof(array) / sizeof(array[0]);
// call the solve function
cout << solve(array, n, k);
return 0;
}
Java
// JAVA Code for Maximum Weight Difference
import java.util.*;
class GFG {
public static int solve(int array[], int n,
int k)
{
// sort the given array
Arrays.sort(array);
// Initializing the value to 0
int sum = 0, sum1 = 0, sum2 = 0;
// Getting the sum of the array
for (int i = 0; i < n; i++) {
sum += array[i];
}
// Getting the sum of first k elements
for (int i = 0; i < k; i++) {
sum1 += array[i];
}
// Getting the sum of (n-k) elements
for (int i = k; i < n; i++) {
sum2 += array[i];
}
// Returning the maximum possible difference.
return Math.max(Math.abs(sum1 - (sum - sum1)),
Math.abs(sum2 - (sum - sum2)));
}
/* Driver program to test above function */
public static void main(String[] args)
{
int k = 2;
int array[] = { 8, 4, 5, 2, 10 };
// calculate the numbers of elements
// in the array
int n = array.length;
// call the solve function
System.out.print(solve(array, n, k));
}
}
// This code is contributed by Arnav Kr. Mandal.
Python
def solve(array, k): # Sorting array array.sort() # Getting the sum of all the elements s = sum(array) # Getting the sum of smallest k elements s1 = sum(array[:k]) # Getting the sum greatest k elements array.sort(reverse=True) s2 = sum(array[:k]) # Returning the maximum possible difference return max(abs(s1-(s-s1)), abs(s2-(s-s2))) # Driver function k = 2 array =[8, 4, 5, 2, 10] print(solve(array, k))
C#
// C# Code for Maximum Weight Difference
using System;
class GFG {
public static int solve(int []array, int n,
int k)
{
// sort the given array
Array.Sort(array);
// Initializing the value to 0
int sum = 0, sum1 = 0, sum2 = 0;
// Getting the sum of the array
for (int i = 0; i < n; i++) {
sum += array[i];
}
// Getting the sum of first k elements
for (int i = 0; i < k; i++) {
sum1 += array[i];
}
// Getting the sum of (n-k) elements
for (int i = k; i < n; i++) {
sum2 += array[i];
}
// Returning the maximum possible difference.
return Math.Max(Math.Abs(sum1 - (sum - sum1)),
Math.Abs(sum2 - (sum - sum2)));
}
/* Driver program to test above function */
public static void Main()
{
int k = 2;
int []array = { 8, 4, 5, 2, 10 };
// calculate the numbers of elements
// in the array
int n = array.Length;
// call the solve function
Console.WriteLine(solve(array, n, k));
}
}
// This code is contributed by vt_m.
PHP
<?php
// PHP Program to find maximum weight
// difference
// return the max value of two numbers
function maxi($a, $b)
{
if ($a > $b)
{
return $a;
}
else
{
return $b;
}
}
function solve(&$arr, $n, $k)
{
// sort the given array
sort($arr);
// Initializing the value to 0
$sum = 0;
$sum1 = 0;
$sum2 = 0;
// Getting the sum of the array
for ($i = 0; $i < $n; $i++)
{
$sum += $arr[$i];
}
// Getting the sum of first k elements
for ($i = 0; $i < $k; $i++)
{
$sum1 += $arr[$i];
}
// Getting the sum of (n-k) elements
for ($i = $k; $i < $n; $i++)
{
$sum2 += $arr[$i];
}
// Returning the maximum possible difference.
return maxi(abs($sum1 - ($sum - $sum1)),
abs($sum2 - ($sum - $sum2)));
}
// DriverCode
$k = 2;
$arr = array(8, 4, 5, 2, 10 );
// calculate the numbers of
// elements in the array
$n = sizeof($arr);
// call the solve function
echo (solve($arr, $n, $k));
// This code is contributed
// by Shivi_Aggarwal
?>
Javascript
<script>
// JavaScript Code for Maximum Weight Difference
function solve(array, n, k)
{
// sort the given array
array.sort(function(a, b){return a - b});
// Initializing the value to 0
let sum = 0, sum1 = 0, sum2 = 0;
// Getting the sum of the array
for (let i = 0; i < n; i++) {
sum += array[i];
}
// Getting the sum of first k elements
for (let i = 0; i < k; i++) {
sum1 += array[i];
}
// Getting the sum of (n-k) elements
for (let i = k; i < n; i++) {
sum2 += array[i];
}
// Returning the maximum possible difference.
return Math.max(Math.abs(sum1 - (sum - sum1)),
Math.abs(sum2 - (sum - sum2)));
}
let k = 2;
let array = [ 8, 4, 5, 2, 10 ];
// calculate the numbers of elements
// in the array
let n = array.length;
// call the solve function
document.write(solve(array, n, k));
</script>
17
Dieser Artikel wurde von Rishabh Bansal beigesteuert . Wenn Ihnen GeeksforGeeks gefällt und Sie etwas beitragen möchten, können Sie auch einen Artikel über write.geeksforgeeks.org schreiben oder Ihren Artikel per E-Mail an review-team@geeksforgeeks.org senden. Sehen Sie, wie Ihr Artikel auf der Hauptseite von GeeksforGeeks erscheint, und helfen Sie anderen Geeks.
Bitte schreiben Sie Kommentare, wenn Sie etwas Falsches finden oder weitere Informationen zu dem oben diskutierten Thema teilen möchten.
Falls Sie an Live-Kursen mit Experten teilnehmen möchten , beziehen Sie sich bitte auf DSA Live-Kurse für Berufstätige und Competitive Programming Live for Students .