Recursion with iteration to implement dynamic programming

Dev Shed Forums Sponsor:

January 20th, 2013, 02:01 AM

yamini.16

Registered User

Join Date: Jan 2013

Posts: 3

Time spent in forums: 26 m 58 sec
Reputation 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 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:

Original - 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

b49P23TIvg

Contributing User

Join Date: Aug 2011

Posts: 3,458

Time spent in forums: 1 Month 2 Weeks 4 Days 6 h 26 m 43 sec
Reputation Power: 403

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!

January 20th, 2013, 05:27 AM