Dadas dos arrays de igual tamaño (A, B) y N (tamaño de ambas arrays).
Una combinación de suma se hace sumando un elemento de la array A y otro elemento de la array B. Muestra el máximo de K combinaciones de suma válidas de todas las combinaciones de suma posibles.
Ejemplos:
Input : A[] : {3, 2}
B[] : {1, 4}
K : 2 [Number of maximum sum
combinations to be printed]
Output : 7 // (A : 3) + (B : 4)
6 // (A : 2) + (B : 4)
Input : A[] : {4, 2, 5, 1}
B[] : {8, 0, 3, 5}
K : 3
Output : 13 // (A : 5) + (B : 8)
12 // (A : 4) + (B : 8)
10 // (A : 2) + (B : 8)
Enfoque 1 (algoritmo ingenuo): podemos usar la fuerza bruta a través de todas las combinaciones posibles que se pueden hacer al tomar un elemento de la array A y otro de la array B e insertarlos en un montón máximo. En un montón máximo, el elemento máximo está en el Node raíz, por lo que cada vez que salimos del montón máximo, obtenemos el elemento máximo presente en el montón. Después de insertar todas las combinaciones de suma, sacamos K elementos del montón máximo y lo mostramos.
A continuación se muestra la implementación del enfoque anterior.
C++
// A simple C++ program to find N maximum
// combinations from two arrays,
#include <bits/stdc++.h>
using namespace std;
// function to display first N maximum sum
// combinations
void KMaxCombinations(int A[], int B[],
int N, int K)
{
// max heap.
priority_queue<int> pq;
// insert all the possible combinations
// in max heap.
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
pq.push(A[i] + B[j]);
// pop first N elements from max heap
// and display them.
int count = 0;
while (count < K) {
cout << pq.top() << endl;
pq.pop();
count++;
}
}
// Driver Code.
int main()
{
int A[] = { 4, 2, 5, 1 };
int B[] = { 8, 0, 5, 3 };
int N = sizeof(A) / sizeof(A[0]);
int K = 3;
// Function call
KMaxCombinations(A, B, N, K);
return 0;
}
Java
// Java program to find K
// maximum combinations
// from two arrays,
import java.io.*;
import java.util.*;
class GFG {
// function to display first K
// maximum sum combinations
static void KMaxCombinations(int A[], int B[],
int N, int K)
{
// max heap.
PriorityQueue<Integer> pq
= new PriorityQueue<Integer>(
Collections.reverseOrder());
// Insert all the possible
// combinations in max heap.
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
pq.add(A[i] + B[j]);
// Pop first N elements
// from max heap and
// display them.
int count = 0;
while (count < K) {
System.out.println(pq.peek());
pq.remove();
count++;
}
}
// Driver Code
public static void main(String[] args)
{
int A[] = { 4, 2, 5, 1 };
int B[] = { 8, 0, 5, 3 };
int N = A.length;
int K = 3;
// Function Call
KMaxCombinations(A, B, N, K);
}
}
// This code is contributed by Mayank Tyagi
Python 3
# Python program to find # K maximum combinations # from two arrays import math from queue import PriorityQueue # Function to display first K # maximum sum combinations def KMaxCombinations(A, B, N, K): # Max heap. pq = PriorityQueue() # Insert all the possible # combinations in max heap. for i in range(0, N): for j in range(0, N): a = A[i] + B[j] pq.put((-a, a)) # Pop first N elements from # max heap and display them. count = 0 while (count < K): print(pq.get()[1]) count = count + 1 # Driver method A = [4, 2, 5, 1] B = [8, 0, 5, 3] N = len(A) K = 3 # Function call KMaxCombinations(A, B, N, K) # This code is contributed # by Gitanjali.
C#
// C# program to find K
// maximum combinations
// from two arrays,
using System;
using System.Collections.Generic;
public class GFG
{
// function to display first K
// maximum sum combinations
static void KMaxCombinations(int []A, int []B,
int N, int K)
{
// max heap.
List<int> pq
= new List<int>();
// Insert all the possible
// combinations in max heap.
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
pq.Add(A[i] + B[j]);
// Pop first N elements
// from max heap and
// display them.
int count = 0;
pq.Sort();
pq.Reverse();
while (count < K)
{
Console.WriteLine(pq[0]);
pq.RemoveAt(0);
count++;
}
}
// Driver Code
public static void Main(String[] args)
{
int []A = { 4, 2, 5, 1 };
int []B = { 8, 0, 5, 3 };
int N = A.Length;
int K = 3;
// Function Call
KMaxCombinations(A, B, N, K);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript program to find K
// maximum combinations
// from two arrays,
// function to display first K
// maximum sum combinations
function KMaxCombinations(A, B, N, K)
{
// max heap.
let pq = [];
// Insert all the possible
// combinations in max heap.
for (let i = 0; i < N; i++)
for (let j = 0; j < N; j++)
pq.push(A[i] + B[j]);
// Pop first N elements
// from max heap and
// display them.
let count = 0;
pq.sort((a, b) => a - b).reverse();
while (count < K)
{
document.write(pq[0] + "<br>");
pq.shift();
count++;
}
}
// Driver Code
let A = [ 4, 2, 5, 1 ];
let B = [ 8, 0, 5, 3 ];
let N = A.length;
let K = 3;
// Function Call
KMaxCombinations(A, B, N, K);
// This code is contributed by gfgking
</script>
Producción
13 12 10
Complejidad del Tiempo: O(N 2 )
Espacio Auxiliar : O(N 2 )
Enfoque 2 (Clasificación, Montón máximo, Mapa):
En lugar de forzar la fuerza bruta a través de todas las posibles combinaciones de sumas, deberíamos encontrar una forma de limitar nuestro espacio de búsqueda a posibles combinaciones de sumas candidatas.
- Ordene ambas arrays, la array A y la array B.
- Cree un montón máximo, es decir, cola de prioridad en C++ para almacenar las combinaciones de suma junto con los índices de los elementos de las arrays A y B que componen la suma. El montón está ordenado por la suma.
- Inicialice el montón con la combinación de suma máxima posible, es decir (A[N – 1] + B[N – 1] donde N es el tamaño de la array) y con los índices de los elementos de ambas arrays (N – 1, N – 1) . La tupla dentro del montón máximo será (A[N-1] + B[N – 1], N – 1, N – 1). El montón está ordenado por el primer valor, es decir, la suma de ambos elementos.
- Haga estallar el montón para obtener la suma más grande actual y junto con los índices del elemento que componen la suma. Sea la tupla (suma, i, j).
- A continuación, inserte (A[i – 1] + B[j], i – 1, j) y (A[i] + B[j – 1], i, j – 1) en el montón máximo, pero asegúrese de que el par de índices, es decir, (i – 1, j) y (i, j – 1) no están
ya presentes en el montón máximo. Para verificar esto, podemos usar set en C++ . - Vuelva a 4 hasta K veces.
- A continuación, inserte (A[i – 1] + B[j], i – 1, j) y (A[i] + B[j – 1], i, j – 1) en el montón máximo, pero asegúrese de que el par de índices, es decir, (i – 1, j) y (i, j – 1) no están
A continuación se muestra la implementación del enfoque anterior:
CPP
// An efficient C++ program to find top K elements
// from two arrays.
#include <bits/stdc++.h>
using namespace std;
// Function prints k maximum possible combinations
void KMaxCombinations(vector<int>& A,
vector<int>& B, int K)
{
// sort both arrays A and B
sort(A.begin(), A.end());
sort(B.begin(), B.end());
int N = A.size();
// Max heap which contains tuple of the format
// (sum, (i, j)) i and j are the indices
// of the elements from array A
// and array B which make up the sum.
priority_queue<pair<int, pair<int, int> > > pq;
// my_set is used to store the indices of
// the pair(i, j) we use my_set to make sure
// the indices does not repeat inside max heap.
set<pair<int, int> > my_set;
// initialize the heap with the maximum sum
// combination ie (A[N - 1] + B[N - 1])
// and also push indices (N - 1, N - 1) along
// with sum.
pq.push(make_pair(A[N - 1] + B[N - 1],
make_pair(N - 1, N - 1)));
my_set.insert(make_pair(N - 1, N - 1));
// iterate upto K
for (int count = 0; count < K; count++)
{
// tuple format (sum, (i, j)).
pair<int, pair<int, int> > temp = pq.top();
pq.pop();
cout << temp.first << endl;
int i = temp.second.first;
int j = temp.second.second;
int sum = A[i - 1] + B[j];
// insert (A[i - 1] + B[j], (i - 1, j))
// into max heap.
pair<int, int> temp1 = make_pair(i - 1, j);
// insert only if the pair (i - 1, j) is
// not already present inside the map i.e.
// no repeating pair should be present inside
// the heap.
if (my_set.find(temp1) == my_set.end())
{
pq.push(make_pair(sum, temp1));
my_set.insert(temp1);
}
// insert (A[i] + B[j - 1], (i, j - 1))
// into max heap.
sum = A[i] + B[j - 1];
temp1 = make_pair(i, j - 1);
// insert only if the pair (i, j - 1)
// is not present inside the heap.
if (my_set.find(temp1) == my_set.end())
{
pq.push(make_pair(sum, temp1));
my_set.insert(temp1);
}
}
}
// Driver Code.
int main()
{
vector<int> A = { 1, 4, 2, 3 };
vector<int> B = { 2, 5, 1, 6 };
int K = 4;
// Function call
KMaxCombinations(A, B, K);
return 0;
}
Java
// An efficient Java program to find
// top K elements from two arrays.
import java.io.*;
import java.util.*;
class GFG {
public static void MaxPairSum(Integer[] A,
Integer[] B,
int N, int K)
{
// sort both arrays A and B
Arrays.sort(A);
Arrays.sort(B);
// Max heap which contains Pair of
// the format (sum, (i, j)) i and j are
// the indices of the elements from
// array A and array B which make up the sum.
PriorityQueue<PairSum> sums
= new PriorityQueue<PairSum>();
// pairs is used to store the indices of
// the Pair(i, j) we use pairs to make sure
// the indices does not repeat inside max heap.
HashSet<Pair> pairs = new HashSet<Pair>();
// initialize the heap with the maximum sum
// combination ie (A[N - 1] + B[N - 1])
// and also push indices (N - 1, N - 1) along
// with sum.
int l = N - 1;
int m = N - 1;
pairs.add(new Pair(l, m));
sums.add(new PairSum(A[l] + B[m], l, m));
// iterate upto K
for (int i = 0; i < K; i++)
{
// Poll the element from the
// maxheap in theformat (sum, (l,m))
PairSum max = sums.poll();
System.out.println(max.sum);
l = max.l - 1;
m = max.m;
// insert only if l and m are greater
// than 0 and the pair (l, m) is
// not already present inside set i.e.
// no repeating pair should be
// present inside the heap.
if (l >= 0 && m >= 0
&& !pairs.contains(new Pair(l, m)))
{
// insert (A[l]+B[m], (l, m))
// in the heap
sums.add(new PairSum(A[l]
+ B[m], l, m));
pairs.add(new Pair(l, m));
}
l = max.l;
m = max.m - 1;
// insert only if l and m are
// greater than 0 and
// the pair (l, m) is not
// already present inside
// set i.e. no repeating pair
// should be present
// inside the heap.
if (l >= 0 && m >= 0
&& !pairs.contains(new Pair(l, m)))
{
// insert (A[i1]+B[i2], (i1, i2))
// in the heap
sums.add(new PairSum(A[l]
+ B[m], l, m));
pairs.add(new Pair(l, m));
}
}
}
// Driver Code
public static void main(String[] args)
{
Integer A[] = { 1, 4, 2, 3 };
Integer B[] = { 2, 5, 1, 6 };
int N = A.length;
int K = 4;
// Function Call
MaxPairSum(A, B, N, K);
}
public static class Pair {
public Pair(int l, int m)
{
this.l = l;
this.m = m;
}
int l;
int m;
@Override public boolean equals(Object o)
{
if (o == null) {
return false;
}
if (!(o instanceof Pair)) {
return false;
}
Pair obj = (Pair)o;
return (l == obj.l && m == obj.m);
}
@Override public int hashCode()
{
return Objects.hash(l, m);
}
}
public static class PairSum
implements Comparable<PairSum> {
public PairSum(int sum, int l, int m)
{
this.sum = sum;
this.l = l;
this.m = m;
}
int sum;
int l;
int m;
@Override public int compareTo(PairSum o)
{
return Integer.compare(o.sum, sum);
}
}
}
Producción
10 9 9 8
Complejidad de tiempo: O(N log N) asumiendo K <= N
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por foreverrookie y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA