Как найти все комбинации, из которых можно составить n?

Question

[dmitriyivvvv]

Добрый вечер! В общем имеется некое множество [100, 50, 25, 10, 5, 1] и n. Мне нужно найти все комбинации, из которых можно составить n. Например для n = 100 и множества выше ответом будет 194 комбинации. Так как с алгоритмами у меня беда, не знаю даже как правильно сформулировать чтобы загуглить.

Comments

[Lynn «Кофеман»]

Искать алгоритм размена монет
И далее по связанным запросам
Например похожая задача math.hashcode.ru/questions/53196/%D0%BA%D0%BE%D0%B...

[Александр Алексеев]

Я не понял, как получилось число 194. Можно пример покороче?

[dmitriyivvvv]

ntllct, 293, я ошибся извиняюсь

Answer 1

[Александр Алексеев]

#include <iostream>
#include <vector>

std::vector<int> arr = { 100, 50, 25, 10, 5, 1 };
int n = 100;
int matches = 0;

void calc( int val, unsigned int offs ) {
  if( val == n ) {
    matches++;
    return;
  } else if( val > n ) {
    return;
  }
  for( unsigned int i = offs; i < arr.size(); ++i ) {
    calc( val + arr[i], i );
  }
}

int main( int argc, char** argv ) {
  calc( 0, 0 );
  std::cout << matches << std::endl;
  return( EXIT_SUCCESS );
}

Answer 2

[Владимир]

Может быть что-то вроде этого: https://prog-cpp.ru/combinations/?

Comments

[longclaps]

нет

[Дмитрий Добрышин]

думаю здесь нечто другое :-)
1. N = 100
2. N = 50 + 50
3. N = 25 + 25 + 50
...
Вероятно простой комбинаторикой здесь не обойтись. Здесь нужна теория графов.

[longclaps]

Дмитрий Добрышин,
думаю здесь нечто другое :-) :-) :-)

[Владимир]

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

[longclaps]

Владимир, спасибо, что присоединились, но ресурсов и правда может не хватить.
Будем ждать решения с перламутровыми пуговицами )

[Владимир]

longclaps, мне кажется, Вам нужно более точно сформулировать задачу. Например, из постановки задачи не понятно как получается число n: только сложение или возможны другие операции? Кроме того, эта задача обязательно должна решаться средствами JS или не обязательно?
А вообще, есть набор значений, из которых можно сложить любое число (при достаточной длине набора) простым сложением, причем каждое число набора будет использовано только один раз. Это классика...)))

[Владимир]

longclaps, вот здесь - opennotes.ru/knowledge/vba-knowledge/algoritm-pois... - приведен похожий алгоритм. Правда, он для VBA, но Вам ведь не решение, а алгоритм нужен?

[longclaps]

Владимир, хех, Фигаро здесь, Фигаро там. Мне всё понятно, но не я - автор вопроса.
Его зовут dmitriyivvvv.

[Владимир]

longclaps, извините, попутал))) Но ведь автору наша дискуссия также доступна, не так ли? )))

[longclaps]

Владимир, а ему без разницы - с алгоритмами у него беда.

[Владимир]

longclaps, ну за что Вы его так? Я уверен, что автор вопроса внимательно читает свой же топик.

[Александр Алексеев]

Дмитрий Добрышин, у меня 293 получилось таким подсчётом (считал программой)

[Дмитрий Добрышин]

ntllct, интересно, сколько при этом у вас было рекомбинаций? :-)

[Александр Алексеев]

Дмитрий Добрышин, для n = 100 и множества [100,50] ответ - 2, если я правильно понял условие задачи. Для [100,50,25] - 4, [100,50,25,10] - 7, [100,50,25,10,5] - 41, [100, 50, 25, 10, 5, 1] - 293
Код:

#include <iostream>
#include <vector>

std::vector<int> arr = { 100, 50, 25, 10, 5, 1 };
int n = 100;
int matches = 0;

void calc( int val, unsigned int offs ) {
	if( val == n ) {
		matches++;
		return;
	} else if( val > n ) {
		return;
	}
	for( unsigned int i = offs; i < arr.size(); ++i ) {
		calc( val + arr[i], i );
	}
}

int main( int argc, char** argv ) {
	calc( 0, 0 );
	std::cout << matches << std::endl;
	return( EXIT_SUCCESS );
}

[dmitriyivvvv]

ntllct, Спасибо, это то что нужно, выложите как ответ, я выберу его в качестве правильного.