最大重量差-yiteyi-C++库

给你一个数组W[1]，W[2]，…，W[N]。在其中选择K个数，使所选数和剩余数之和之间的绝对差尽可能大。 例如：

null

Input : arr[] = [8, 4, 5, 2, 10]            k = 2Output: 17Input : arr[] = [1, 1, 1, 1, 1, 1, 1, 1]          k = 3Output: 2

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

有两种可能得到想要的答案。这两个是：选择 K 最大数字或选择 K 最小的数字。根据给定值选择最合适的选项。这是因为在某些情况下，最小k个数的和可以大于数组的其余部分，而在某些情况下，最大k个数的和可以大于数组的其余部分。 方法：

对给定数组进行排序。
获取数组中所有数字的总和并将其存储在总和
得到第一个 K 数组的编号并将其存储在 sum1
得到最后一个数的总和 K 数组的编号并将其存储在 sum2
输出以下结果： 最大值（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>                       

输出

本文由 里沙布·班萨尔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章