VPF::Вычисление всех возможных вариантов

Abbath1349

Дата 8.10.2011, 09:25 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 214
Регистрация: 16.6.2010

Репутация: нет
Всего: нет

у меня есть массив из чисел например {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 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 194
Регистрация: 31.5.2003

Репутация: 2
Всего: 4

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

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

--------------------

B.Sc ->M.Sc.->Microsoft SDE-> (Ph.D. student + Intel SDE + psyсhology B.A) - > Skype SDET

Abbath1349

Дата 8.10.2011, 10:16 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 214
Регистрация: 16.6.2010

Репутация: нет
Всего: нет

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

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

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

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

Lipetsk

Дата 8.10.2011, 10:20 (ссылка)

(нет голосов)

Загрузка ...

в форме ;)

Профиль
Группа: Участник
Сообщений: 180
Регистрация: 28.1.2009
Где: Липецк

Репутация: 2
Всего: 5

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

esperanto

Дата 8.10.2011, 11:00 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 194
Регистрация: 31.5.2003

Репутация: 2
Всего: 4

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

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

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

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

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

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

--------------------

B.Sc ->M.Sc.->Microsoft SDE-> (Ph.D. student + Intel SDE + psyсhology B.A) - > Skype SDET

Abbath1349

Дата 8.10.2011, 15:20 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 214
Регистрация: 16.6.2010

Репутация: нет
Всего: нет

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

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

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

sQu1rr

Дата 11.10.2011, 20:15 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 597
Регистрация: 11.11.2008
Где: london

Репутация: нет
Всего: 13

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

)

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

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

sQu1rr

Дата 11.10.2011, 21:42 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 597
Регистрация: 11.11.2008
Где: london

Репутация: нет
Всего: 13

Если не повторяются, то вот базовый вариант

Код


#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 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 61
Регистрация: 15.11.2006

Репутация: 1
Всего: 1

Предлагаю упрощенную реализацию
Всё зависит очень сильно от размера массива, но для массивов меньших 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 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 157
Регистрация: 15.9.2008

Репутация: нет
Всего: 1

Цитата(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. тогда перебирать придется меньше.

--------------------

Oaks may fall when reeds stand the storm.

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Алгоритмы \| Следующая тема »