通过从第一和第二阵列中选取X和Y元素，最大化X+Y元素的总和-yiteyi-C++库

给定两个大小为N的数组，以及两个数字X和Y，任务是通过考虑以下几点来最大化总和：

null

选择十、来自第一个数组和 Y 第二个数组中的值，使X+Y值之和最大。
给出了X+Y等于N。

例如：

输入： arr1[]={1,4,1}，arr2[]={2,5,3}，N=3，X=2，Y=1 输出： 8. 为了使两个数组的和最大化，从第一个数组中选择第一和第二个元素，从第二个数组中选择第三个元素。

输入： A[]={1,4,1,2}，B[]={4,3,2,5}，N=4，X=2，Y=2 输出： 14

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

方法： 贪婪的方法可以用来解决上述问题。以下是所需的步骤：

通过查找两个数组元素之间的最大差异，首先查找具有最大值的数组元素。
为此，请找到第一个数组和第二个数组的值之间的绝对差，然后将其存储在另一个数组中。
按降序排列此数组。
排序时，跟踪数组中元素的原始位置。
现在比较两个数组的元素，并将较大的值添加到maxAmount。
如果两者的值相同，则在X不为零时添加第一个数组的元素，否则添加第二个数组的元素。
遍历数组后，完全返回maxAmount计算值。

以下是上述方法的实施情况：

C++

                         // C++ program to print the maximum                       
                         // possible sum from two arrays.                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // class that store values of two arrays                       
                         // and also store their absolute difference                       
                         class                                     triplet {                       
                         public                                     :                       
                                                 int                                     first;                       
                                                 int                                     second;                       
                                                 int                                     diff;                       
                                                 triplet(                                     int                                     f,                                     int                                     s,                                     int                                     d)                       
                                                 : first(f), second(s), diff(d)                       
                                                 {                       
                                                 }                       
                         };                       
           
                         // Compare function used to sort array in decreasing order                       
                         bool                                     compare(triplet& a, triplet& b)                       
                         {                       
                                                 return                                     a.diff > b.diff;                                     // decreasing order                       
                         }                       
           
                         /// Function to find the maximum possible                       
                         /// sum that can be generated from 2 arrays                       
                         int                                     findMaxAmount(                                     int                                     arr1[],                                     int                                     arr2[],                                     int                                     n,                                     int                                     x,                                     int                                     y)                       
                         {                       
                                                 // vector where each index stores 3 things:                       
                                                 // Value of 1st array                       
                                                 // Value of 2nd array                       
                                                 // Their absolute difference                       
                                                 vector<triplet> v;                       
           
                                                 for                                     (                                     int                                     i = 0; i < n; i++) {                       
                                                 triplet t(arr1[i], arr2[i],                                     abs                                     (arr1[i] - arr2[i]));                       
                                                 v.push_back(t);                       
                                                 }                       
           
                                                 // sort according to their absolute difference                       
                                                 sort(v.begin(), v.end(), compare);                       
           
                                                 // it will store maximum sum                       
                                                 int                                     maxAmount = 0;                       
           
                                                 int                                     i = 0;                       
           
                                                 // Run loop for N times or                       
                                                 // value of X or Y becomes zero                       
                                                 while                                     (i < n && x > 0 && y > 0) {                       
           
                                                 // if 1st array element has greater                       
                                                 // value, add it to maxAmount                       
                                                 if                                     (v[i].first > v[i].second) {                       
                                                 maxAmount += v[i].first;                       
                                                 x--;                       
                                                 }                       
           
                                                 // if 2nd array element has greater                       
                                                 // value, add it to maxAmount                       
                                                 if                                     (v[i].first < v[i].second) {                       
                                                 maxAmount += v[i].second;                       
                                                 y--;                       
                                                 }                       
           
                                                 // if both have same value, add element                       
                                                 // of first array if X is not zero                       
                                                 // else add element of second array                       
                                                 if                                     (v[i].first == v[i].second) {                       
                                                 if                                     (x > 0) {                       
                                                 maxAmount += v[i].first;                       
                                                 x--;                       
                                                 }                       
                                                 else                                     if                                     (y > 0) {                       
                                                 maxAmount += v[i].second;                       
                                                 y--;                       
                                                 }                       
                                                 }                       
           
                                                 // increment after picking element                       
                                                 i++;                       
                                                 }                       
           
                                                 // add the remaining values                       
                                                 // of first array to maxAmount                       
                                                 while                                     (i < v.size() && x--) {                       
                                                 maxAmount += v[i++].first;                       
                                                 }                       
           
                                                 // add the remaining values of                       
                                                 // second array to maxAmount                       
                                                 while                                     (i < v.size() && y--) {                       
                                                 maxAmount += v[i++].second;                       
                                                 }                       
           
                                                 return                                     maxAmount;                       
                         }                       
           
                         // Driver Code                       
                         int                                     main()                       
                         {                       
                                                 int                                     A[] = { 1, 4, 1, 2 };                       
                                                 int                                     B[] = { 4, 3, 2, 5 };                       
                                                 int                                     n =                                     sizeof                                     (A) /                                     sizeof                                     (A[0]);                       
           
                                                 int                                     X = 2, Y = 2;                       
           
                                                 cout << findMaxAmount(A, B, n, X, Y) <<                                     ""                                     ;                       
                         }                       

JAVA

                         // Java program to print the maximum                       
                         // possible sum from two arrays.                       
                         import                                     java.util.*;                       
           
                         // class that store values of two arrays                       
                         // and also store their absolute difference                       
                         class                                     Triplet                                     implements                                     Comparable<Triplet>                       
                         {                       
                                                 int                                     first;                       
                                                 int                                     second;                       
                                                 int                                     diff;                       
           
                                                 Triplet(                                     int                                     f,                                     int                                     s,                                     int                                     d)                       
                                                 {                       
                                                 first = f;                       
                                                 second = s;                       
                                                 diff = d;                       
                                                 }                       
                                   
                                                 // CompareTo function used to sort                       
                                                 // array in decreasing order                       
                                                 public                                     int                                     compareTo(Triplet o)                       
                                                 {                       
                                                 return                                     o.diff -                                     this                                     .diff;                       
                                                 }                       
                         }                       
                         class                                     GFG{                       
           
                         // Function to find the maximum possible                       
                         // sum that can be generated from 2 arrays                       
                         public                                     static                                     int                                     findMaxAmount(                                     int                                     arr1[],                       
                                                 int                                     arr2[],                       
                                                 int                                     n,                                     int                                     x,                       
                                                 int                                     y)                       
                         {                       
                                   
                                                 // Vector where each index                       
                                                 // stores 3 things:                       
                                                 // Value of 1st array                       
                                                 // Value of 2nd array                       
                                                 // Their absolute difference                       
                                                 Vector<Triplet> v =                                     new                                     Vector<>();                       
           
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < n; i++)                       
                                                 {                       
                                                 v.add(                                     new                                     Triplet(arr1[i], arr2[i],                       
                                                 Math.abs(arr1[i] -                       
                                                 arr2[i])));                       
                                                 }                       
           
                                                 // Sort according to their                       
                                                 // absolute difference                       
                                                 Collections.sort(v);                       
           
                                                 // It will store maximum sum                       
                                                 int                                     maxAmount =                                     0                                     ;                       
           
                                                 int                                     i =                                     0                                     ;                       
           
                                                 // Run loop for N times or                       
                                                 // value of X or Y becomes zero                       
                                                 while                                     (i < n && x >                                     0                                     && y >                                     0                                     )                       
                                                 {                       
                                   
                                                 // If 1st array element has greater                       
                                                 // value, add it to maxAmount                       
                                                 if                                     (v.get(i).first > v.get(i).second)                       
                                                 {                       
                                                 maxAmount += v.get(i).first;                       
                                                 x--;                       
                                                 }                       
           
                                                 // If 2nd array element has greater                       
                                                 // value, add it to maxAmount                       
                                                 if                                     (v.get(i).first < v.get(i).second)                       
                                                 {                       
                                                 maxAmount += v.get(i).second;                       
                                                 y--;                       
                                                 }                       
                                   
                                                 // If both have same value, add element                       
                                                 // of first array if X is not zero                       
                                                 // else add element of second array                       
                                                 if                                     (v.get(i).first == v.get(i).second)                       
                                                 {                       
                                                 if                                     (x >                                     0                                     )                       
                                                 {                       
                                                 maxAmount += v.get(i).first;                       
                                                 x--;                       
                                                 }                       
                                                 else                                     if                                     (y >                                     0                                     )                       
                                                 {                       
                                                 maxAmount += v.get(i).second;                       
                                                 y--;                       
                                                 }                       
                                                 }                       
                                   
                                                 // Increment after picking element                       
                                                 i++;                       
                                                 }                       
           
                                                 // Add the remaining values                       
                                                 // of first array to maxAmount                       
                                                 while                                     (i < v.size() && x-- >                                     0                                     )                       
                                                 {                       
                                                 maxAmount += v.get(i++).first;                       
                                                 }                       
           
                                                 // Add the remaining values of                       
                                                 // second array to maxAmount                       
                                                 while                                     (i < v.size() && y-- >                                     0                                     )                       
                                                 {                       
                                                 maxAmount += v.get(i++).second;                       
                                                 }                       
                                   
                                                 return                                     maxAmount;                       
                         }                       
           
                         // Driver Code                       
                         public                                     static                                     void                                     main(String []args)                       
                         {                       
                                                 int                                     A[] = {                                     1                                     ,                                     4                                     ,                                     1                                     ,                                     2                                     };                       
                                                 int                                     B[] = {                                     4                                     ,                                     3                                     ,                                     2                                     ,                                     5                                     };                       
                                                 int                                     n = A.length;                       
           
                                                 int                                     X =                                     2                                     , Y =                                     2                                     ;                       
           
                                                 System.out.println(findMaxAmount(A, B, n, X, Y));                       
                         }                       
                         }                       
           
                         // This code is contributed by jrishabh99                       

Python3

                         # Python3 program to print the maximum                       
                         # possible sum from two arrays.                       
           
                         # Class that store values of two arrays                       
                         # and also store their absolute difference                       
                         class                                     triplet:                       
                                   
                                                 def                                     __init__(                                     self                                     , f, s, d):                       
                                                 self                                     .first                                     =                                     f                       
                                                 self                                     .second                                     =                                     s                       
                                                 self                                     .diff                                     =                                     d                       
           
                         # Function to find the maximum possible                       
                         # sum that can be generated from 2 arrays                       
                         def                                     findMaxAmount(arr1, arr2, n, x, y):                       
           
                                                 # vector where each index stores 3 things:                       
                                                 # Value of 1st array                       
                                                 # Value of 2nd array                       
                                                 # Their absolute difference                       
                                                 v                                     =                                     []                       
           
                                                 for                                     i                                     in                                     range                                     (                                     0                                     , n):                       
                                                 t                                     =                                     triplet(arr1[i], arr2[i],                       
                                                 abs                                     (arr1[i]                                     -                                     arr2[i]))                       
                                                 v.append(t)                       
           
                                                 # sort according to their absolute difference                       
                                                 v.sort(key                                     =                                     lambda                                     x: x.diff, reverse                                     =                                     True                                     )                       
           
                                                 # it will store maximum sum                       
                                                 maxAmount, i                                     =                                     0                                     ,                                     0                       
           
                                                 # Run loop for N times or                       
                                                 # value of X or Y becomes zero                       
                                                 while                                     i < n                                     and                                     x >                                     0                                     and                                     y >                                     0                                     :                       
           
                                                 # if 1st array element has greater                       
                                                 # value, add it to maxAmount                       
                                                 if                                     v[i].first > v[i].second:                       
                                                 maxAmount                                     +                                     =                                     v[i].first                       
                                                 x                                     -                                     =                                     1                       
           
                                                 # if 2nd array element has greater                       
                                                 # value, add it to maxAmount                       
                                                 if                                     v[i].first < v[i].second:                       
                                                 maxAmount                                     +                                     =                                     v[i].second                       
                                                 y                                     -                                     =                                     1                       
           
                                                 # if both have same value, add element                       
                                                 # of first array if X is not zero                       
                                                 # else add element of second array                       
                                                 if                                     v[i].first                                     =                                     =                                     v[i].second:                       
                                                 if                                     x >                                     0                                     :                       
                                                 maxAmount                                     +                                     =                                     v[i].first                       
                                                 x                                     -                                     =                                     1                       
                                   
                                                 elif                                     y >                                     0                                     :                       
                                                 maxAmount                                     +                                     =                                     v[i].second                       
                                                 y                                     -                                     =                                     1                       
           
                                                 # increment after picking element                       
                                                 i                                     +                                     =                                     1                       
                                   
                                                 # add the remaining values                       
                                                 # of first array to maxAmount                       
                                                 while                                     i <                                     len                                     (v)                                     and                                     x >                                     0                                     :                       
                                                 maxAmount                                     +                                     =                                     v[i].first                       
                                                 i, x                                     =                                     i                                     +                                     1                                     , x                                     -                                     1                       
           
                                                 # add the remaining values of                       
                                                 # second array to maxAmount                       
                                                 while                                     i <                                     len                                     (v)                                     and                                     y >                                     0                                     :                       
                                                 maxAmount                                     +                                     =                                     v[i].second                       
                                                 i, y                                     =                                     i                                     +                                     1                                     , y                                     -                                     1                       
                                   
                                                 return                                     maxAmount                       
           
                         # Driver Code                       
                         if                                     __name__                                     =                                     =                                     "__main__"                                     :                       
           
                                                 A                                     =                                     [                                     1                                     ,                                     4                                     ,                                     1                                     ,                                     2                                     ]                       
                                                 B                                     =                                     [                                     4                                     ,                                     3                                     ,                                     2                                     ,                                     5                                     ]                       
                                                 n                                     =                                     len                                     (A)                       
           
                                                 X, Y                                     =                                     2                                     ,                                     2                       
           
                                                 print                                     (findMaxAmount(A, B, n, X, Y))                       
           
                         # This code is contributed by Rituraj Jain                       

输出：

时间复杂性： O（N日志N） 辅助空间： O（N）

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

THE END

技术文章