Dado un conjunto de n enteros donde n <= 40. Cada uno de ellos es como máximo 10 12 , determine el subconjunto de suma máxima que tenga una suma menor o igual a S donde S <= 10 18 .
Ejemplo:
Input : set[] = {45, 34, 4, 12, 5, 2} and S = 42
Output : 41
Maximum possible subset sum is 41 which can be
obtained by summing 34, 5 and 2.
Input : Set[] = {3, 34, 4, 12, 5, 2} and S = 10
Output : 10
Maximum possible subset sum is 10 which can be
obtained by summing 2, 3 and 5.
Un enfoque de fuerza bruta para resolver este problema sería encontrar todas las sumas de subconjuntos posibles de N enteros y verificar si es menor o igual a S y realizar un seguimiento de dicho subconjunto con la suma máxima. La complejidad del tiempo utilizando este enfoque sería O(2 n ) y n es como máximo 40. 2 40 será bastante grande y, por lo tanto, necesitamos encontrar un enfoque más óptimo.
Meet in the middle es una técnica de búsqueda que se usa cuando la entrada es pequeña pero no tan pequeña como para que se pueda usar la fuerza bruta. Al igual que divide y vencerás, divide el problema en dos, los resuelve individualmente y luego los fusiona. Pero no podemos aplicar el encuentro en el medio como divide y vencerás porque no tenemos la misma estructura que el problema original.
- Divida el conjunto de enteros en 2 subconjuntos, digamos A y B. A tiene los primeros n/2 enteros y B tiene el resto.
- Encuentre todas las posibles sumas de subconjuntos de enteros en el conjunto A y almacene en una array X. De manera similar, calcule todas las posibles sumas de subconjuntos de enteros en el conjunto B y almacene en la array Y. Por lo tanto, el tamaño de cada una de las arrays X e Y será como máximo 2 n/2 .
- Ahora combine estos 2 subproblemas. Encuentre combinaciones de arrays X e Y tales que su suma sea menor o igual que S.
- Una forma de hacerlo es simplemente iterar sobre todos los elementos de la array Y para cada elemento de la array X para verificar la existencia de dicha combinación. Esto tomará O( (2 n/2 ) 2 ) que es equivalente a O(2 n ).
- Para hacerlo menos complejo, primero ordene la array Y y luego itere sobre cada elemento de X y para cada elemento x en X use la búsqueda binaria para encontrar el elemento máximo y en Y tal que x + y <= S.
- La búsqueda binaria aquí ayuda a reducir la complejidad de 2 n a 2 n/2 log(2 n/2 ) que es equivalente a 2 n/2 n.
- Por lo tanto, nuestro tiempo de ejecución final es O (2 n/2 n).
C++
// C++ program to demonstrate working of Meet in the
// Middle algorithm for maximum subset sum problem.
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll X[2000005],Y[2000005];
// Find all possible sum of elements of a[] and store
// in x[]
void calcsubarray(ll a[], ll x[], int n, int c)
{
for (int i=0; i<(1<<n); i++)
{
ll s = 0;
for (int j=0; j<n; j++)
if (i & (1<<j))
s += a[j+c];
x[i] = s;
}
}
// Returns the maximum possible sum less or equal to S
ll solveSubsetSum(ll a[], int n, ll S)
{
// Compute all subset sums of first and second
// halves
calcsubarray(a, X, n/2, 0);
calcsubarray(a, Y, n-n/2, n/2);
int size_X = 1<<(n/2);
int size_Y = 1<<(n-n/2);
// Sort Y (we need to do doing binary search in it)
sort(Y, Y+size_Y);
// To keep track of the maximum sum of a subset
// such that the maximum sum is less than S
ll max = 0;
// Traverse all elements of X and do Binary Search
// for a pair in Y with maximum sum less than S.
for (int i=0; i<size_X; i++)
{
if (X[i] <= S)
{
// lower_bound() returns the first address
// which has value greater than or equal to
// S-X[i].
int p = lower_bound(Y, Y+size_Y, S-X[i]) - Y;
// If S-X[i] was not in array Y then decrease
// p by 1
if (p == size_Y || Y[p] != (S-X[i]))
p--;
if ((Y[p]+X[i]) > max)
max = Y[p]+X[i];
}
}
return max;
}
// Driver code
int main()
{
ll a[] = {3, 34, 4, 12, 5, 2};
int n=sizeof(a)/sizeof(a[0]);
ll S = 10;
printf("Largest value smaller than or equal to given "
"sum is %lld\n", solveSubsetSum(a,n,S));
return 0;
}
Java
// Java program to demonstrate working of
// Meet in the Middle algorithm for
// maximum subset sum problem
import java.util.*;
import java.lang.*;
import java.io.*;
class GFG{
static long X[] = new long[2000005];
static long Y[] = new long[2000005];
// Find all possible sum of elements of a[]
// and store in x[]
static void calcsubarray(long a[],long x[],
int n, int c)
{
for(int i = 0; i < (1 << n); i++)
{
long s = 0;
for(int j = 0; j < n; j++)
if ((i & (1 << j)) == 1)
s += a[j + c];
x[i] = s;
}
}
// Returns the maximum possible sum
// less or equal to S
static long solveSubsetSum(long a[], int n, long S)
{
// Compute all subset sums of first and second
// halves
calcsubarray(a, X, n / 2, 0);
calcsubarray(a, Y, n - n / 2, n / 2);
int size_X = 1 << (n / 2);
int size_Y = 1 << (n - n / 2);
// Sort Y (we need to do doing
// binary search in it)
Arrays.sort(Y);
// To keep track of the maximum sum
// of a subset such that the maximum
// sum is less than S
long max = 0;
// Traverse all elements of X and do
// Binary Search for a pair in Y with
// maximum sum less than S.
for(int i = 0; i < size_X; i++)
{
if (X[i] <= S)
{
// lower_bound() returns the first address
// which has value greater than or equal to
// S-X[i].
int p = lower_bound(Y, S - X[i]);
// If S-X[i] was not in array Y then
// decrease p by 1
if (p == size_Y || Y[p] != (S - X[i]))
p--;
if ((Y[p] + X[i]) > max)
max = Y[p] + X[i];
}
}
return max;
}
static int lower_bound(long a[], long x)
{
// x is the target value or key
int l = -1, r = a.length;
while (l + 1 < r)
{
int m = (l + r) >>> 1;
if (a[m] >= x)
r = m;
else
l = m;
}
return r;
}
// Driver code
public static void main (String[] args)
{
long a[] = { 3, 34, 4, 12, 5, 2 };
int n = a.length;
long S = 10;
System.out.println("Largest value smaller " +
"than or equal to given " +
"sum is " +
solveSubsetSum(a, n, S));
}
}
// This code is contributed by jyoti369
Python3
# Python program to demonstrate working of Meet in the
# Middle algorithm for maximum subset sum problem.
from typing import List
import bisect
X = [0] * 2000005
Y = [0] * 2000005
# Find all possible sum of elements of a[] and store
# in x[]
def calcsubarray(a: List[int], x: List[int], n: int, c: int) -> None:
for i in range((1 << n)):
s = 0
for j in range(n):
if (i & (1 << j)):
s += a[j + c]
x[i] = s
# Returns the maximum possible sum less or equal to S
def solveSubsetSum(a: List[int], n: int, S: int) -> int:
global Y
# Compute all subset sums of first and second
# halves
calcsubarray(a, X, n // 2, 0)
calcsubarray(a, Y, n - n // 2, n // 2)
size_X = 1 << (n // 2)
size_Y = 1 << (n - n // 2)
# Sort Y (we need to do doing binary search in it)
YY = Y[:size_Y]
YY.sort()
Y = YY
# To keep track of the maximum sum of a subset
# such that the maximum sum is less than S
maxx = 0
# Traverse all elements of X and do Binary Search
# for a pair in Y with maximum sum less than S.
for i in range(size_X):
if (X[i] <= S):
# lower_bound() returns the first address
# which has value greater than or equal to
# S-X[i].
p = bisect.bisect_left(Y, S - X[i])
# If S-X[i] was not in array Y then decrease
# p by 1
if (p == size_Y or (p < size_Y and Y[p] != (S - X[i]))):
p -= 1
if ((Y[p] + X[i]) > maxx):
maxx = Y[p] + X[i]
return maxx
# Driver code
if __name__ == "__main__":
a = [3, 34, 4, 12, 5, 2]
n = len(a)
S = 10
print("Largest value smaller than or equal to given sum is {}".format(
solveSubsetSum(a, n, S)))
# This code is contributed by sanjeev2552
C#
// C# program to demonstrate working of
// Meet in the Middle algorithm for
// maximum subset sum problem
using System;
public class GFG
{
static long[] X = new long[2000005];
static long[] Y = new long[2000005];
// Find all possible sum of elements of a[]
// and store in x[]
static void calcsubarray(long[] a,long[] x,
int n, int c)
{
for(int i = 0; i < (1 << n); i++)
{
long s = 0;
for(int j = 0; j < n; j++)
if ((i & (1 << j)) == 1)
s += a[j + c];
x[i] = s;
}
}
// Returns the maximum possible sum
// less or equal to S
static long solveSubsetSum(long[] a, int n, long S)
{
// Compute all subset sums of first and second
// halves
calcsubarray(a, X, n / 2, 0);
calcsubarray(a, Y, n - n / 2, n / 2);
int size_X = 1 << (n / 2);
int size_Y = 1 << (n - n / 2);
// Sort Y (we need to do doing
// binary search in it)
Array.Sort(Y);
// To keep track of the maximum sum
// of a subset such that the maximum
// sum is less than S
long max = 0;
// Traverse all elements of X and do
// Binary Search for a pair in Y with
// maximum sum less than S.
for(int i = 0; i < size_X; i++)
{
if (X[i] <= S)
{
// lower_bound() returns the first address
// which has value greater than or equal to
// S-X[i].
int p = lower_bound(Y, S - X[i]);
// If S-X[i] was not in array Y then
// decrease p by 1
if (p == size_Y || Y[p] != (S - X[i]))
p--;
if ((Y[p] + X[i]) > max)
max = Y[p] + X[i];
}
}
return max;
}
static int lower_bound(long[] a, long x)
{
// x is the target value or key
int l = -1, r = a.Length;
while (l + 1 < r)
{
int m = (l + r) >> 1;
if (a[m] >= x)
r = m;
else
l = m;
}
return r;
}
// Driver code
static public void Main ()
{
long[] a = { 3, 34, 4, 12, 5, 2 };
int n = a.Length;
long S = 10;
Console.WriteLine("Largest value smaller " +
"than or equal to given " +
"sum is " +
solveSubsetSum(a, n, S));
}
}
// This code is contributed by Dharanendra L V.
Javascript
<script>
// Javascript program to demonstrate working of
// Meet in the Middle algorithm for
// maximum subset sum problem
let X = new Array(2000005);
let Y = new Array(2000005);
for(let i = 0; i < 2000005; i++)
{
X[i] = 0;
Y[i] = 0;
}
// Find all possible sum of elements of a[]
// and store in x[]
function calcsubarray(a, x, n, c)
{
for(let i = 0; i < (1 << n); i++)
{
let s = 0;
for(let j = 0; j < n; j++)
if ((i & (1 << j)) == 1)
s += a[j + c];
x[i] = s;
}
}
// Returns the maximum possible sum
// less or equal to S
function solveSubsetSum(a,n,S)
{
// Compute all subset sums of first and second
// halves
calcsubarray(a, X, Math.floor(n / 2), 0);
calcsubarray(a, Y, n - Math.floor(n / 2), Math.floor(n / 2));
let size_X = 1 << Math.floor(n / 2);
let size_Y = 1 << (n - Math.floor(n / 2));
// Sort Y (we need to do doing
// binary search in it)
Y.sort(function(a,b){return a-b;});
// To keep track of the maximum sum
// of a subset such that the maximum
// sum is less than S
let max = 0;
// Traverse all elements of X and do
// Binary Search for a pair in Y with
// maximum sum less than S.
for(let i = 0; i < size_X; i++)
{
if (X[i] <= S)
{
// lower_bound() returns the first address
// which has value greater than or equal to
// S-X[i].
let p = lower_bound(Y, S - X[i]);
// If S-X[i] was not in array Y then
// decrease p by 1
if (p == size_Y || Y[p] != (S - X[i]))
p--;
if ((Y[p] + X[i]) > max)
max = Y[p] + X[i];
}
}
return max;
}
function lower_bound(a,x)
{
// x is the target value or key
let l = -1, r = a.length;
while (l + 1 < r)
{
let m = (l + r) >>> 1;
if (a[m] >= x)
r = m;
else
l = m;
}
return r;
}
// Driver code
let a=[3, 34, 4, 12, 5, 2 ];
let n = a.length;
let S = 10;
document.write("Largest value smaller " +
"than or equal to given " +
"sum is " +
solveSubsetSum(a, n, S)+"<br>");
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
Largest value smaller than or equal to given sum is 10
Referencia:
Complejidad de tiempo: O( 
)
Espacio auxiliar: O( 
)
Este artículo es una contribución de Madhur Modi . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA