Количество способов такое, что сумма k элементов равна p

Question

Данная серия целых чисел, имеющих отношение, где число равно сумме двух предыдущих чисел, а начальное целое число равно 1

Серия ->1,2,3,5,8,13,21,34,55

найти число способов, чтобы сумма k элементов равнялась p. Мы можем использовать элемент любое количество раз.

р =8

к =4.

Таким образом, количество способов будет 4. Эти

1,1,1,5

1,1,3,3

1,2,2,3

2,2,2,2

Я могу решить этот вопрос с помощью рекурсии. Я чувствую динамическое программирование здесь, но я не понимаю, как это сделать. Может ли это быть сделано за гораздо меньшее время???

РЕДАКТИРОВАТЬ Я забыл упомянуть, что последовательность чисел не имеет значения и будет учтена один раз. для ex=3->(1,2) и (2,1). здесь число путей будет только 1.

Answer 1

Вы можете использовать динамическое программирование. Позволять C(p, k) быть количество способов, которые суммируют k элемент, равный p а также a быть массивом элементов. затем

 C(p, k) = C(p - a[0], k - 1) + C(p - a[1], k - 1) + .... + C(p - a[n-1], k - 1)

Затем вы можете использовать запоминание, чтобы ускорить ваш код.

Answer 2

Подсказка:

Ваша проблема хорошо известна. Это проблема сумм, вариация задачи о ранце. Проверьте это довольно хорошее объяснение. проблема сумм

Answer 3

РЕДАКТИРОВАТЬ: Постер изменил первоначальную проблему, так как это было опубликовано. Мой алгоритм все еще работает, но, возможно, может быть улучшен. Исходная задача имела n произвольных входных чисел (теперь он изменил ее, чтобы она была последовательностью Фибоначчи). Чтобы применить мой алгоритм к измененному посту, обрежьте ряд, взяв только элементы меньше p (предположим, что их n).

Вот n^(k/2) алгоритм. (n это количество элементов в серии)

Используйте таблицу длины pтакой, что table[i] содержит все комбинации k/2 элементы, которые в сумме i, Например, в примере данных, которые вы предоставили, table[4] содержит {1,3} а также {2,2},

РЕДАКТИРОВАТЬ: Если пространство запрещено, этот же алгоритм может быть выполнен с упорядоченными связанными списками, где вы храните только непустые записи таблицы. Связанный список должен быть в обоих направлениях: вперед и назад, что делает последний шаг алгоритма чище.

Как только эта таблица вычислена, мы получаем все решения, комбинируя table[j] с каждым table[p-j]всякий раз, когда оба не пусты.

Чтобы получить таблицу, инициализируйте всю вещь, чтобы очистить. Затем:

For i_1 = 0 to n-1:
    For i_2 = i_1 to n-1:
        ...
            For i_k/2 = i_k/2-1 to n-1:
                sum = series[i_1] + ... + series[i_k/2]
                    if sum <= p:
                        store {i_1, i_2, ... , i_k/2 } in table[sum]

Это "переменное число циклов" выглядит невозможным для реализации, но на самом деле это может быть сделано с массивом длины k/2 это отслеживает, где находится каждый i_`.

Давайте вернемся к вашим данным и посмотрим, как будет выглядеть наша таблица:

table[2] = {1,1}
table[3] = {1,2}
table[4] = {1,3} and {2,2}
table[5] = {2,3}
table[6] = {1,5}
table[7] = {2,5}
table[8] = {3,5}

Решения найдены путем объединения table[2] с table[6], table[3] с table[5], а также table[4] с table[4], Таким образом, решения: {1,1,1,5} {1,2,2,3}, {1,1,3,3}, {2,2,2,2}, {1,3,2,2}.