Комбинации алгоритма массива

Question

Я хотел бы найти комбинации из массива размера 5, который добавляет до 15. Каков наилучший способ сделать это.

Предположим, у меня есть массив

7 8 10 5 3

Какой самый лучший способ найти все числа, которые складываются до 15 в C ++

Answer 1

Сортировка массива элементов.поддерживать два указателя, один в начале отсортированного массива, а другой в конце.если сумма двух элементов больше 15, уменьшите 2-й указатель.если сумма меньше 15, увеличьте 1-й указатель.если сумма равна 15, запишите два элемента и увеличьте 1-й указатель.

Надеюсь, это сработает.

Answer 2

Если, как вы упомянули в своем комментарии, 10 - это наибольшее число в задаче (также максимальное количество элементов). Тогда грубая сила (с умной битовой маскировкой, см. этот урок ) сделает:

// N is the number of elements and arr is the array.
for (int i = 0; i < (1 << N); ++i) {
    int sum = 0;
    for (int j = 0; j < N; ++j) if (i & (1 << j)) sum += arr[j];
    if (sum == required_sum); // Do something with the subset represented by i.
}

Этот алгоритм имеет сложность O (N * 2 ^ N). Обратите внимание, что код верен до тех пор, пока N <32. Обратите внимание, что количество подмножеств с определенной суммой может быть экспоненциальным (более 2 ^ (N / 2)). Пример, {1, 1, 1, 1, .., 1} и сумма = N / 2. </p>

Если, однако, N велико, но N * required_sum не очень велико (до миллионов), можно использовать следующее повторение (с динамическим программированием или запоминанием):

f(0, 0) = 1
f(0, n) = 0 where n > 0
f(k, n) = 0 where k < 0
f(k + 1, S) = f(k, S - arr[k]) + f(k, S) where k >= 0

где f (k, S) обозначает возможность получения суммы S с подмножеством элементов 0..k. Динамическая таблица программирования может использоваться для генерации всех подмножеств. Время генерации таблицы составляет O (N * S), где S - требуемая сумма. Время генерации подмножеств из таблицы пропорционально количеству таких подмножеств (которое может быть очень большим).

Общие замечания по проблеме:

Проблема в общем случае NP-Complete . Следовательно, он не имеет известного алгоритма полиномиального времени. Тем не менее, он имеет алгоритм псевдополиномиального времени , а именно повторение выше.

Answer 3

я предлагаю пойти на рекурсию.

отслеживая базовый индекс и текущий индекс и пытаться накапливать значения каждую рекурсию

возвращать целочисленное значение текущего индекса, если накопленное значение равно 15 остальнымесли currentindex достигает 5 и накопленное значение не равно 15, верните 0

, когда return равно 0, а baseindex все еще меньше 5, затем добавьте 1 к базовому индексу, сбросьте текущий индекс и накопленное значение и снова запустите рекурсию.

Answer 4

«лучший» способ зависит от того, что вы оптимизируете.

Если в массиве не так много элементов, существует простой комбинаторный алгоритм: для всех длин от 1 до n (где n - это количество элементов в массиве), проверьте все возможные наборы n чисел и напечатайте каждое, сумма которого равна пятнадцати.

Это, вероятно, будет наилучшим с точки зрения времени реализации.Решение с динамическим программированием (это проблема DP), вероятно, будет лучшим с точки зрения эффективности времени выполнения;решение DP здесь O(N³), где комбинаторное решение намного больше этого.

Суть алгоритма DP (я не пишу код) состоит в том, чтобы просмотреть ваш массив и сохранитьотслеживать все возможные суммы, которые можно сделать с помощью подмассива, который вы уже видели.Когда вы достигнете каждого нового элемента массива, просмотрите все полученные ранее частичные суммы и добавьте их к ним (не удаляя исходную частичную сумму).Всякий раз, когда что-то достигает 15 или проходит его, отбросьте эту сумму из набора, который вы отслеживаете (выведите его, если оно точно достигнет 15).

Answer 5

Рекурсия - один из вариантов, который я могу придумать.Поскольку у меня было немного свободного времени, я собрал эту функцию (хотя она, вероятно, излишне велика и неоптимизирована до крайности).Я проверил его только с указанными вами числами.

void getCombinations( std::vector<int>& _list, std::vector<std::vector<int>>& _output, 
                      std::vector<int>& _cSumList = std::vector<int>(), int _sum = 0 )
{
    for ( std::vector<int>::iterator _it = _list.begin(); _it < _list.end(); ++_it)
    {
        _sum += *_it;
        _cSumList.push_back( *_it );
        std::vector<int> _newList;
        for ( std::vector<int>::iterator _itn = _list.begin(); _itn < _list.end(); ++_itn )
            if ( *_itn != *_it )
                _newList.push_back( *_itn );
        if ( _sum < 15 )
            getCombinations( _newList, _output, _cSumList, _sum );
        else if ( _sum == 15 )
        {
            bool _t = false;
            for ( std::vector<std::vector<int>>::iterator _itCOutputList = _output.begin(); _itCOutputList < _output.end(); ++_itCOutputList )
            {
                unsigned _count = 0;
                for ( std::vector<int>::iterator _ita = _itCOutputList->begin(); _ita < _itCOutputList->end(); ++_ita )
                    for ( std::vector<int>::iterator _itb = _cSumList.begin(); _itb < _cSumList.end(); ++_itb )
                        if ( *_itb == *_ita )
                            ++_count;
                if ( _count == _cSumList.size() )
                    _t = true;
            }
            if ( _t == false )
                _output.push_back( _cSumList );
        }
        _cSumList.pop_back();
        _sum -= *_it;
    }
}

Пример использования с вашими номерами:

int _tmain(int argc, _TCHAR* argv[])
{
    std::vector<int> list;
    list.push_back( 7 );
    list.push_back( 8 );
    list.push_back( 10 );
    list.push_back( 5 );
    list.push_back( 3 );
    std::vector<std::vector<int>> output;
    getCombinations( list, output );
    for ( std::vector<std::vector<int>>::iterator _it = output.begin(); _it < output.end(); ++_it)
    {
        for ( std::vector<int>::iterator _it2 = (*_it).begin(); _it2 < (*_it).end(); ++_it2)
            std::cout << *(_it2) << ",";
        std::cout << "\n";
    }
    std::cin.get();
    return 0;
}

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