Thread: Recursion with iteration to implement dynamic programming

1. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Jan 2013
Posts
3
Rep Power
0

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&nbsp;row&nbsp;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.
2. 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".
3. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Jan 2013
Posts
3
Rep Power
0
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.