2
When $K = N$, the polynomial you are trying to compute is known as the permanent. The best algorithms for computing the permanent use $\tilde{O}(2^N)$ arithmetic operations, see Wikipedia. The VP≠VNP conjecture implies that the permanent cannot be computed using a polynomial number of operations.
For general $K$, your function is a known extension of the ...
1
Here is some pseudocode that illustrates the recursive idea.
If you choose to take this element, then you have to skip ahead 6 steps.
Otherwise you skip this element and go to the next.
def solve(array, index):
if index >= len(array):
return 0
this_one = array[index] # the value x_i
opt_five_steps = solve(array, ...
1
I don't have a dynamic programming solution but this problem can be efficiently reduced to a minimum weight max-flow problem.
Let $G$ denote your original graph. We will create an instance $(s,t,G')$ of the minimum weight max-flow problem as follows:
Let $W$ denote the sum of all weights in $G$ plus one.
For every vertex $u$ in $G$, we create two vertices $...
1
Lets deal with the issues one at a time, since there are a few of them.
Problem 1
Take a look at those lines of code:
trow = [0] * (m+1)
table = [trow] * (n+1)
srow = [""] * (m+1)
solution = [srow] * (n+1)
The problem with this code, is that the same list is being placed a few times. This means, that every list in $table$ must be all ...
1
Programming questions are off-topic here.
Anyway your matrices table and solution are not properly initialized as they contain references to the same objects. Try:
table = [[0]*(m+1) for j in range(n+1)]
solution = [ ["" for i in range(m+1)] for j in range(n+1) ]
Moreover, the returned string should be solution[n][m] and not solution[n-1][...
Only top voted, non community-wiki answers of a minimum length are eligible
