Для игры, которую я делаю, у меня есть ситуация, где у меня есть список чисел – говорят [7, 4, 9, 1, 15, 2] (названный A
для этого) – и другой список чисел – говорят [11, 18, 14, 8, 3] (названный B
) – если мне. Цель состоит в том, чтобы найти все комбинации чисел в A
это составляет в целом число в B
. Например:
... и так далее. (В целях этого, 1 + 2
совпадает с 2 + 1
.)
Для маленьких списков как это это тривиально только к "в лоб" комбинации, но я сталкиваюсь с возможностью наблюдения тысяч к десяткам тысяч этих чисел и буду использовать эту стандартную программу неоднократно по продолжительности жизни приложения. Действительно ли там кто-либо - вид изящного алгоритма, доступного для выполнения этого в разумный срок с 100%-м покрытием? В случае неудачи есть ли какой-либо вид достойной эвристики, я могу найти, что это может дать мне "достаточно хороший" набор комбинаций за разумное количество времени?
Я ищу алгоритм в псевдокоде, или на любом прилично популярном и читаемом языке (отметьте "и" там.... ;) или даже просто английское описание того, как можно было бы пойти о реализации этого вида поиска.
Отредактированный для добавления:
Большая хорошая информация предоставляется до сих пор. Спасибо парень! Суммирование на данный момент:
Сохраните прибытие идей! И еще раз спасибо!
Эта проблема является NP-полной ... Это некая вариация задачи суммы подмножества, которая известна как NP-Complete (на самом деле задача суммы подмножества проще, чем ваша).
Подробнее читайте здесь: http://en.wikipedia.org/wiki/Subset_sum_problem
Это небольшое обобщение проблемы суммы подмножеств. В общем случае она NP-полна, но пока все числа целые и максимальное число в B
относительно невелико, псевдополиномиальное решение, описанное в статье Википедии, на которую я дал ссылку, должно помочь.
Как было сказано в комментариях с числами от 1 до 30, проблема имеет быстрое решение. Я протестировал его на C, и для приведенного вами примера ему нужны лишь милисекунды, и он очень хорошо масштабируется. Сложность составляет O(n+k), где n - длина списка A
, а k - длина списка B
, но с высоким постоянным коэффициентом (существует 28.598 возможностей получить сумму от 1 до 30).
#define WIDTH 30000
#define MAXNUMBER 30
int create_combination(unsigned char comb[WIDTH][MAXNUMBER+1],
int n,
unsigned char i,
unsigned char len,
unsigned char min,
unsigned char sum) {
unsigned char j;
if (len == 1) {
if (n+1>=WIDTH) {
printf("not enough space!\n");
exit(-1);
}
comb[n][i] = sum;
for (j=0; j<=i; j++)
comb[n+1][j] = comb[n][j];
n++;
return n;
}
for (j=min; j<=sum/len; j++) {
comb[n][i] = j;
n = create_combination(comb, n, i+1, len-1, j, sum-j);
}
return n;
}
int main(void)
{
unsigned char A[6] = { 7, 4, 9, 1, 15, 2 };
unsigned char B[5] = { 11, 18, 14, 8, 3 };
unsigned char combinations[WIDTH][MAXNUMBER+1];
unsigned char needed[WIDTH][MAXNUMBER];
unsigned char numbers[MAXNUMBER];
unsigned char sums[MAXNUMBER];
unsigned char i, j, k;
int n=0, m;
memset(combinations, 0, sizeof combinations);
memset(needed, 0, sizeof needed);
memset(numbers, 0, sizeof numbers);
memset(sums, 0, sizeof sums);
// create array with all possible combinations
// combinations[n][0] stores the sum
for (i=2; i<=MAXNUMBER; i++) {
for (j=2; j<=i; j++) {
for (k=1; k<=MAXNUMBER; k++)
combinations[n][k] = 0;
combinations[n][0] = i;
n = create_combination(combinations, n, 1, j, 1, i);
}
}
// count quantity of any summands in each combination
for (m=0; m<n; m++)
for (i=1; i<=MAXNUMBER && combinations[m][i] != 0; i++)
needed[m][combinations[m][i]-1]++;
// count quantity of any number in A
for (m=0; m<6; m++)
if (numbers[A[m]-1] < MAXNUMBER)
numbers[A[m]-1]++;
// collect possible sums from B
for (m=0; m<5; m++)
sums[B[m]-1] = 1;
for (m=0; m<n; m++) {
// check if sum is in B
if (sums[combinations[m][0]-1] == 0)
continue;
// check if enough summands from current combination are in A
for (i=0; i<MAXNUMBER; i++) {
if (numbers[i] < needed[m][i])
break;
}
if (i<MAXNUMBER)
continue;
// output result
for (j=1; j<=MAXNUMBER && combinations[m][j] != 0; j++) {
printf(" %s %d", j>1 ? "+" : "", combinations[m][j]);
}
printf(" = %d\n", combinations[m][0]);
}
return 0;
}
1 + 2 = 3
1 + 7 = 8
2 + 9 = 11
4 + 7 = 11
1 + 4 + 9 = 14
1 + 2 + 4 + 7 = 14
1 + 2 + 15 = 18
2 + 7 + 9 = 18
Похоже на проблему с рюкзаком (см. http://en.wikipedia.org/wiki/Knapsack_problem . На этой странице они также объясняют, что проблема является NP-полной. в общем.
Я думаю, это означает, что если вы хотите найти ВСЕ допустимые комбинации, вам просто нужно много времени.