Встретиться посередине

Опубликовано: 20 Января, 2022

Дан набор из n целых чисел, где n <= 40. Каждое из них не больше 10 ¹² , определите подмножество максимальной суммы, имеющее сумму меньше или равную S, где S <= 10 ¹⁸ .

Пример:

 Ввод: установите [] = {45, 34, 4, 12, 5, 2} и S = 42.
Выход: 41
Максимально возможная сумма подмножества 41, которая может быть 
получается суммированием 34, 5 и 2.

Ввод: Установите [] = {3, 34, 4, 12, 5, 2} и S = 10.
Выход: 10
Максимально возможная сумма подмножества составляет 10, что может быть 
получается суммированием 2, 3 и 5.

Подход грубой силы для решения этой проблемы заключается в том, чтобы найти все возможные суммы подмножества из N целых чисел и проверить, меньше ли оно или равно S, и отслеживать такое подмножество с максимальной суммой. Временная сложность при использовании этого подхода будет O (2 ⁿ ), а n не превосходит 40. 2 ⁴⁰ будет довольно большим, и, следовательно, нам нужно найти более оптимальный подход.

Meet in the middle is a search technique which is used when the input is small but not as small that brute force can be used. Like divide and conquer it splits the problem into two, solves them individually and then merge them. But we can’t apply meet in the middle like divide and conquer because we don’t have the same structure as the original problem.

Split the set of integers into 2 subsets say A and B. A having first n/2 integers and B having rest.
Find all possible subset sums of integers in set A and store in an array X. Similarly calculate all possible subset sums of integers in set B and store in array Y. Hence, Size of each of the array X and Y will be at most 2^n/2.
Now merge these 2 subproblems. Find combinations from array X and Y such that their sum is less than or equal to S.
- One way to do that is simply iterate over all elements of array Y for each element of array X to check the existence of such a combination. This will take O( (2^n/2)²) which is equivalent to O(2ⁿ).
- To make it less complex, first sort array Y and then iterate over each element of X and for each element x in X use binary search to find maximum element y in Y such that x + y <= S.
- Binary search here helps in reducing complexity from 2ⁿto 2^n/2log(2^n/2)which is equivalent to 2^n/2n.
- Thus our final running time is O(2^n/2n).

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
", 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)) == 0)
                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)) == 0)
          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.

Выход:

Largest value smaller than or equal to given sum is 10

Ссылка:

https://www.quora.com/What-is-meet-in-the-middle-algorithm-wrt-competitive-programming

Эта статья предоставлена Мадуром Моди . Если вам нравится GeeksforGeeks, и вы хотели бы внести свой вклад, вы также можете написать статью и отправить ее по электронной почте на deposit@geeksforgeeks.org. Посмотрите, как ваша статья появляется на главной странице GeeksforGeeks, и помогите другим гикам.
Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсужденной выше

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подго

Алгоритмы

Встретиться посередине

C++

Java

Python3

C#

РЕКОМЕНДУЕМЫЕ СТАТЬИ