Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Вычисление всех возможных вариантов

Автор: Abbath1349 8.10.2011, 09:25

у меня есть массив из чисел например {1,4,67,8,9,4,7,8,4,7,3,5} и число например 20 как мне найти все варианты чисел < 20 которые можно получить при складывании?
что то вроде:
1+4+5+7=17
8+7+3=18
....

Автор: esperanto 8.10.2011, 09:46

Можно получить все числа меньшие 20, так как у вас есть 1

1
2=1+1
3=1+1+1
....

Автор: Abbath1349 8.10.2011, 10:16

Цитата(esperanto @ 8.10.2011, 09:46)

Можно получить все числа меньшие 20, так как у вас есть 1

1
2=1+1
3=1+1+1
....

Я имел ввиду при складывании определенной части цифр из данного массива

Автор: Lipetsk 8.10.2011, 10:20

полным перебором 2^n вариантов
хотя такой перебор легко оптимизировать

Автор: esperanto 8.10.2011, 11:00

Цитата(Abbath1349 @ 8.10.2011, 10:16)

Цитата(esperanto @ 8.10.2011, 09:46)

Можно получить все числа меньшие 20, так как у вас есть 1

1
2=1+1
3=1+1+1
....

Я имел ввиду при складывании определенной части цифр из данного массива

1 это и есть определеная часть элементов из массива

Автор: Abbath1349 8.10.2011, 15:20

Цитата(Lipetsk @ 8.10.2011, 10:20)

полным перебором 2^n вариантов
хотя такой перебор легко оптимизировать

а по подробнее можно?

Автор: sQu1rr 11.10.2011, 20:15

Цитата(Abbath1349 @ 8.10.2011, 09:25

)

которые можно получить при складывании?

повторяца числа из массива не могут? я иммею ввиду, если в массив {4,4}, то варианты только 4 и 4+4 ?

Автор: sQu1rr 11.10.2011, 21:42

Если не повторяются, то http://liveworkspace.org/code/5dc2ae159bb8c717835ffd25c1d6af3e базовый вариант

Код


#include <iostream>
#include <algorithm>
#include <set>

const int limit = 20;
int arr[] = {1, 4, 67, 8, 9, 4, 7, 8, 4, 7, 3, 5};
int len = sizeof(arr)/sizeof(arr[0]);
std::set<int> s;

bool solve(int sum, int i)
{
    if(sum >= limit) return false;
    s.insert(sum);
    while(++i < len && solve(sum+arr[i], i));
    return true;
}

int main()
{
    std::sort(arr, arr+len);
    while(len > 0 && arr[len-1] >= limit) --len;
    for(int i = 0; i < len; ++i) solve(arr[i], i);
    for(auto i = s.begin(); i != s.end(); ++i) std::cout << *i << std::endl;
}

С++, но помоему смысл понятен.
Если объем выборки больше (ну и разумеется лимит), ну, всмысле намного больше, ооочень намного, то приедтся оптимизировать, а так сойдет

Автор: comp 13.11.2011, 03:09

Предлагаю упрощенную реализацию
Всё зависит очень сильно от размера массива, но для массивов меньших 20 будет работать отлично.
Весь массив можно представить в виде двоичного числа, а отдельную ячейку в виде отдельного бита. Если этот бит равен 0 -- то число не учитывается, если 1 -- то учитывается. Тогда вся задача сводится к проходу в цикле от 1 до 2^n, где n -- размер массива.

ну и код получается следующий

Код


m -- наш массив
n -- размер массива
limit -- критерий

for( int i = 0; i < (1<<n); ++i ) -- проходимся в цикле с 0 до 2^n
{
  int s = 0;
  for( int j = 0; j < n; ++j ) if( i & (1 << j) ) -- проверяем j-ю ячейку массива
    s += m[j];
  if(s < limit)
  {
    for( int j = 0; j < n; ++j ) if( i & (1<<j) )
      printf("%d ", m[j]);
    printf("\n");
  }
}

Автор: миг 13.11.2011, 11:50

Цитата(Abbath1349 @ 8.10.2011, 09:25

)

у меня есть массив из чисел например {1,4,67,8,9,4,7,8,4,7,3,5} и число например 20

Цитата(Lipetsk @ 8.10.2011, 10:20

)

полным перебором 2^n вариантов
хотя такой перебор легко оптимизировать

но лучше отсортировать числа в порядке возрастания или хотя бы выкинуть из массива все числа, которые уже больше или равны 20. тогда перебирать придется меньше.