Дан бесконечный массив положительных целых чисел или, скажем, поток положительных целых чисел, найдите первые пять чисел, сумма которых равна двадцати.
При чтении условия задачи сначала кажется, что 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
, все еще существует вероятность того, что первый вызов никогда не вернется. Есть ли способ применить алгоритм рюкзака
в таких сценариях?