CODEWITHSUNDEEP
pythonalgorithm
Sunner
Sunner

Reputation: 3

Output error is 0x03BB7390

def fastMaxVal(w, v, i, aW):
    global numCalls
    numCalls += 1
    try: return m[(i, aW)]
    except KeyError:
        if i == 0:
            if w[i] <= aW:
                m[(i, aW)] = v[i]
                return v[i]
            else:
                m[(i, aW)] = 0
                return 0
        without_i = fastMaxVal(w, v, i-1, aW)
        if w[i] > aW:
            m[(i, aW)] = without_i
            return without_i
        else:
            with_i = v[i] + fastMaxVal(w, v, i-1, aW - w[i])
        res = max(with_i, without_i)
        m[(i, aW)] = res
        return res

def maxVal0(w, v, i, aW):
    m = {}
    return fastMaxVal

weights = [1, 1, 5, 5, 3, 3, 4, 4]
vals = [15, 15, 10, 10, 9, 9, 5, 5]
numCalls = 0
res = maxVal0(weights, vals, len(vals) - 1, 8)
print ('max Val =', res, 'number of calls =', numCalls)

The program is about 01Knapsack problem. I use the decision tree to solve the problem. However, I ran the program and got the following result.

max Val = function fastMaxVal at 0x03BB7390 number of calls = 0

What's wrong with my program?

Upvotes: 0

Views: 48

Answers (2)

Sunner
Sunner

Reputation: 3

def fastMaxVal(w, v, i, aW, m):
    global numCalls
    numCalls += 1
    try: return m[(i, aW)]
    except KeyError:
        if i == 0:
            if w[i] <= aW:
                m[(i, aW)] = v[i]
                return v[i]
            else:
                m[(i, aW)] = 0
                return 0
        without_i = fastMaxVal(w, v, i-1, aW, m)
        if w[i] > aW:
            m[(i, aW)] = without_i
            return without_i
        else:
            with_i = v[i] + fastMaxVal(w, v, i-1, aW - w[i], m)
        res = max(with_i, without_i)
        m[(i, aW)] = res
        return res

def maxVal0(w, v, i, aW):
    m = {}
    return fastMaxVal(w, v, i, aW, m)

weights = [1, 1, 5, 5, 3, 3, 4, 4]
vals = [15, 15, 10, 10, 9, 9, 5, 5]
numCalls = 0
res = maxVal0(weights, vals, len(vals) - 1, 8)
print ('max Val =', res, 'number of calls =', numCalls)

I put the right on the above. And I attached the result as follows.

max Val = 48 number of calls = 50

Upvotes: 0

Styx
Styx

Reputation: 10076

In your maxVal0 function you're returning the fastMaxVal function itself, instead of its call result.

I think it should be like this:

def maxVal0(w, v, i, aW):
    m = {}
    return fastMaxVal(w, v, i, aW)

Also, your fastMaxVal is using m, but it isn't in its scope.

Upvotes: 1

Related Questions