Найти набор чисел в одной коллекции, который складывается в число в другой

Question

Для игры, которую я делаю, у меня есть ситуация, когда у меня есть список чисел - скажем, [7, 4, 9, 1, 15, 2] (для этого назван A) - и другой список чисел- скажем [11, 18, 14, 8, 3] (названный B) - предоставлено мне.Цель состоит в том, чтобы найти все комбинации чисел в A, которые складываются в число в B.Например:

• 1 + 2 = 3
• 1 + 7 = 8
• 2 + 9 = 11
• 4 + 7 = 11
• 1 + 2 + 4 + 7 = 14
• 1 + 2 + 15 = 18
• 2 + 7 + 9 = 18

...и так далее.(Для этого 1 + 2 - это то же самое, что и 2 + 1.)

Для небольших списков, подобных этому, тривиально просто комбинировать комбинации, но я сталкиваюсь с возможностью увидеть тысячидо десятков тысяч из этих чисел и будут использовать эту процедуру неоднократно в течение срока службы приложения.Есть ли какой-нибудь элегантный алгоритм для достижения этого в разумные сроки со 100% охватом?Если это не удастся, есть ли какая-нибудь достойная эвристика, которую я могу найти, которая может дать мне «достаточно хороший» набор комбинаций за разумное время?

Я ищу алгоритм в псевдокоде илина любом прилично популярном и читаемом языке (обратите внимание на «и» там ....;) или даже просто на английском языке описание того, как можно было бы реализовать этот вид поиска.

---

Отредактировано, чтобы добавить:

Много хорошей информации, предоставленной до сих пор.Спасибо, парень!Подводя итоги:

• Проблема в NP-Complete, так что нет никакой возможности перебрать грубую силу, чтобы получить 100% точность в разумные сроки.
• Проблему можно рассматривать каквариант проблем с подмножеством или рюкзак .Для обеих систем существуют хорошо известные эвристики, которые могут быть адаптированы к этой проблеме.

Продолжайте воплощать идеи в жизнь!И еще раз спасибо!

Answer 1

Эта задача является NP-полной ... Это некоторая разновидность задачи с подмножеством, которая известна как NP-полная (на самом деле, проблема с подмножеством проще, чем ваша).

Читайте здесь для получения дополнительной информации: http://en.wikipedia.org/wiki/Subset_sum_problem

Answer 2

Как сказано в комментариях с номерами от 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

Answer 3

Это небольшое обобщение задачи о подмножестве сумм .Как правило, оно является NP-полным, но пока все числа являются целыми числами, а максимальное число в B относительно мало, псевдополиномиальное решение, описанное в статье Википедии, которую я связал, должно сработать.

Answer 4

Звучит как проблема с рюкзаком (см. http://en.wikipedia.org/wiki/Knapsack_problem.. На этой странице они также объясняют, что проблема в целом является NP-полной.

Я думаю, это означает, что если вы хотите найти ВСЕ действительнымикомбинации, вам просто нужно много времени.