Рубрики

Встретимся в середине

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

Пример:

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.

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

Встреча в середине — это техника поиска, которая используется, когда ввод небольшой, но не такой маленький, чтобы можно было использовать грубую силу. Как и разделяй и властвуй, он разбивает проблему на две части, решает их индивидуально, а затем объединяет. Но мы не можем применить встречу в середине, как разделяй и властвуй, потому что у нас нет той же структуры, что и у исходной задачи.

  • Разбейте набор целых чисел на 2 подмножества, скажем, A и B. A, имеющий первые n / 2 целых числа, и B, имеющий остаток.
  • Найдите все возможные суммы подмножеств целых чисел в множестве A и сохраните их в массиве X. Аналогичным образом вычислите все возможные суммы подмножеств целых чисел в множестве B и сохраните в массиве Y. Следовательно, размер каждого из массивов X и Y будет не более 2 н / 2 .
  • Теперь объедините эти 2 подзадачи. Найдите комбинации из массива X и Y так, чтобы их сумма была меньше или равна S.
    • Один из способов сделать это — просто перебрать все элементы массива Y для каждого элемента массива X, чтобы проверить существование такой комбинации. Это займет O ((2 n / 2 ) 2 ), что эквивалентно O (2 n ).
    • Чтобы сделать его менее сложным, сначала сортируйте массив Y, а затем итерируйте по каждому элементу X и для каждого элемента x в X используйте бинарный поиск, чтобы найти максимальный элемент y в Y, такой что x + y
    • Бинарный поиск здесь помогает уменьшить сложность с 2 n до 2 n / 2 log (2 n / 2 ), что эквивалентно 2 n / 2 n.
    • Таким образом, наше окончательное время работы O (2 н / 2 н).

// C ++ программа для демонстрации работы Meet в
// Средний алгоритм для задачи с максимальной суммой подмножеств.
#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;

ll X[2000005],Y[2000005];

  
// Находим всю возможную сумму элементов a [] и храним
// в х []

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;

    }

}

  
// Возвращает максимально возможную сумму, меньшую или равную S

ll solveSubsetSum(ll a[], int n, ll S)

{

    // Вычисляем все суммы подмножеств первой и второй

    // половинки

    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);

  

    // Сортировка Y (нам нужно выполнить бинарный поиск в нем)

    sort(Y, Y+size_Y);

  

    // Отслеживать максимальную сумму подмножества

    // такой, что максимальная сумма меньше S

    ll max = 0;

  

    // Обходим все элементы X и делаем бинарный поиск

    // для пары в Y с максимальной суммой меньше S.

    for (int i=0; i<size_X; i++)

    {

        if (X[i] <= S)

        {

            // lower_bound () возвращает первый адрес

            // значение которого больше или равно

            // SX [i].

            int p = lower_bound(Y, Y+size_Y, S-X[i]) - Y;

  

            // Если SX [i] не было в массиве Y, тогда уменьшаем

            // p на 1

            if (p == size_Y || Y[p] != (S-X[i]))

                p--;

  

            if ((Y[p]+X[i]) > max)

                max = Y[p]+X[i];

        }

    }

    return max;

}

  
// Код драйвера

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;

}

Выход:

Largest value smaller than or equal to given sum is 10

Ссылка:

Эта статья предоставлена Мадхур Моди . Если вам нравится GeeksforGeeks и вы хотите внести свой вклад, вы также можете написать статью и отправить ее по почте на contrib@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Встретимся в середине

0.00 (0%) 0 votes