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

    Join Date
    Jan 2013
    Posts
    3
    Rep Power
    0

    Question 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.
  2. #2
  3. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,900
    Rep Power
    481
    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!
  4. #3
  5. 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.

IMN logo majestic logo threadwatch logo seochat tools logo