Number of ways such that sum of k elements equal t

问题:

Given series of integers having relation where a number is equal to sum of previous 2 numbers and starting integer is 1

Series ->1,2,3,5,8,13,21,34,55

find the number of ways such that sum of k elements equal to p.We can use an element any number of times.

p=8

k=4.

So,number of ways would be 4.Those are,

1,1,1,5

1,1,3,3

1,2,2,3

2,2,2,2

I am able to sove this question through recursion.I sense dynamic programming here but i am not getting how to do it.Can it be done in much lesser time???

EDIT I forgot to mention that the sequence of the numbers does not matter and will be counted once. for ex=3->(1,2)and(2,1).here number of ways would be 1 only.

回答1:

EDIT: Poster has changed the original problem since this was posted. My algorithm still works, but maybe can be improved upon. Original problem had n arbitrary input numbers (he has now modified it to be a Fibonacci series). To apply my algorithm to the modified post, truncate the series by taking only elements less than p (assume there are n of them).

Here's an n^(k/2) algorithm. (n is the number of elements in the series)

Use a table of length p, such that table[i] contains all combinations of k/2 elements that sum to i. For example, in the example data that you provided, table[4] contains {1,3} and {2,2}.

EDIT: If the space is prohibitive, this same algorithm can be done with an ordered linked lists, where you only store the non-empty table entries. The linked list has to be both directions: forward and backwards, which makes the final step of the algorithm cleaner.

Once this table is computed, then we get all solutions by combining every table[j] with every table[p-j], whenever both are non-empty.

To get the table, initialize the entire thing to empty. Then:

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]

This "variable number of loops" looks impossible to implement, but actually it can be done with an array of length k/2 that keeps track of where each i_` is.

Let's go back to your data and see how our table would look:

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}

Solutions are found by combining table[2] with table[6], table[3] with table[5], and table[4] with table[4]. Thus, solutions are: {1,1,1,5} {1,2,2,3}, {1,1,3,3}, {2,2,2,2}, {1,3,2,2}.

回答2:

You can use dynamic programming. Let C(p, k) be the number of ways that sum k element equal to p and a be the array of elements. Then

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

Then, you can use memorization to speed up your code.

回答3:

Hint:

Your problem is well-known. It is the sum set problem, a variation of knapsack problem. Check this pretty good explanation. sum-set problem