Tag Info

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