擅长:python、mysql、java
<pre><code>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)
</code></pre>
<p>我把右边放在上面。我附上结果如下</p>
<blockquote>
<p>max Val = 48 number of calls = 50</p>
</blockquote>