January 20th, 2013, 02:01 AM

Recursion with iteration to implement dynamic programming
I have to implement a dynamic programming technique to solve the problem of selecting exactly one element from a row and column of a matrix such that the sum is minimum. I am using the formula:
cost(r,set)=min {m[r][j]+cost(r+1,set[j])} where j is an element of set and terminal condition: cost(4,[ ])=0.
The following code works fine for length of set =3 but fails in l=4. Kindly help if you can.
code Code:
def cost(r,set):
if r==4:
return 0
else:
l=len(set)
for j in range (l):
temp=[]
ab=[]
#if l !=1:
#for k in range (l):
a=set[j]
for o in range (l):
if set[o] != a:
temp.append(set[o])
#print temp
x = mse[r][a]+cost(r+1,temp)
for i in range (1,l):
if l%(i+1)==0:
#print x
ab.append(x)
print ab
if l==2:
#print "In loop"
mini=min(ab)
ans.append(mini)
ab=[]
ab.append(mini)
else:
if l==3:
#print "In else if"
mini=min(ab)
del ans[0:l]
ans.append(mini)
ab=[]
ab.append(mini)
if l==4:
#print "In else if"
mini=min(ab)
del ans[0:l]
ans.append(mini)
ab=[]
ab.append(mini)
#print "In else else"
#x=min([ans])
#ans=[]
#ans.append(x)
return x
mse=[[],[],[],[]]
mse[0]=[10,4,2,4]
mse[1]=[0,0,0,0]
mse[2]=[4,1,0,1]
mse[3]=[0,1,4,9]
global ans
ans=[]
set=[2,3]
#print len(set)
#print set[1]
#print len(set[1])
x=cost(2,set)
print x
print ans
l=len(ans)
where mse is the matrix for which the solution is to be found.
January 20th, 2013, 05:21 AM

Please, what does "set[j]" mean?
The global statement is useful in functions, but not at the module level.
set is a builtin type. Hiding meaning with a variable named set is usually a bad idea.
The minimum sum of your mse matrix is 3. Correct?
Using "l" as a variable name is a nasty practice, because it's hard to read. I use "L" when "l" seems right.
Otherwise, I've never solved this problem for large matrices so I'm unlikely to help even if you address these issues. Sorry. It sure does seem like there's a more efficient algorithm than "try every possibility".
[code]
Code tags[/code] are essential for python code and Makefiles!
January 20th, 2013, 05:27 AM

yes it is 3.
set  j indicates the entire set except the element with value =j.
I have used lists in order to implement it.