0-1 Рюкзак в бесконечном целочисленном массиве?

Дан бесконечный массив положительных целых чисел или, скажем, поток положительных целых чисел, найдите первые пять чисел, сумма которых равна двадцати.

При чтении условия задачи сначала кажется, что 0-1 Knapsackзадача, но я не понимаю, можно ли 0-1 алгоритм Knapsackиспользовать в потоке целых чисел. . Предположим, я пишу рекурсивную программу для вышеуказанной задачи.

int knapsack(int sum, int count, int idx)
{
    if (sum == 0 && count == 0)
        return 1;

    if ((sum == 0 && count != 0) || (sum != 0 && count == 0))
        return 0;

    if (arr[idx] > 20) //element cann't be included.
        return knapsack(sum, count idx + 1);

    return max(knapsack(sum, count, idx +1), knapsack(sum - arr[idx], count -1, idx + 1));
} 

Теперь, когда вышеуказанная функция будет вызывать бесконечный массив, первый вызов функции max, т.е. knapsack(sum, count, idx +1), никогда не вернется, поскольку продолжайте игнорировать текущий элемент. Даже если мы изменим порядок вызова в функции max, все еще существует вероятность того, что первый вызов никогда не вернется. Есть ли способ применить алгоритм рюкзакав таких сценариях?

5
задан Ravi Gupta 13 May 2012 в 05:46
поделиться