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
Related Tags
dynamic-programming × 739algorithms × 429
optimization × 85
graphs × 59
knapsack-problems × 55
recursion × 51
greedy-algorithms × 51
combinatorics × 31
algorithm-analysis × 30
recurrence-relation × 29
data-structures × 28
subsequences × 26
strings × 23
time-complexity × 22
shortest-path × 20
trees × 19
arrays × 19
matrices × 18
runtime-analysis × 15
memoization × 15
correctness-proof × 14
binary-trees × 13
scheduling × 13
backtracking × 13
complexity-theory × 12