def square(x):
y = x*x
return y
def factorial(n):
f = 1
for j in range(2,n+1):
f = f*j
return f
def factorial2(n):
if n == 0 or n == 1:
return 1
else:
return n*factorial2(n-1)
# Minimal Studying
probs = [
[.2,.3,.35,.38,.4],
[.25,.3,.33,.35,.38],
[.1,.3,.4,.45,.5]
]
_minstudy = {}
def minstudy(j,s):
if j == 3:
return (1, None)
else:
#return min(((1 – probs[j][a])*minstudy(j+1,s-a)[0],a,s-a) for a in range(s+1))
if (j,s) not in _minstudy:
best = (1, None)
for a in range(s+1):
p = (1 – probs[j][a])*minstudy(j+1,s-a)[0]
if p < best[0]:
best = (p, a, s-a)
_minstudy[j,s]= best
return _minstudy[j,s]
# Knapsack Problem
sizes = [7,4,3]
values = [25,12,8]
def knapsack(j,s):
if j == 3:
return (0, 'Done')
else:
best = (0, 0, s)
for a in range(s//sizes[j]+1):
y = values[j]*a + knapsack(j+1,s - sizes[j]*a)[0]
if y > best[0]:
best = (y, a, s-sizes[j]*a)
return best
def knapsacksol(total):
s = total
for j in range(3):
v = knapsack(j,s)
if j == 0:
print(“Max value is”,v[0])
print(“Pack”,v[1],”of item”,j)
s = v[2]
_knap = {}
def knap(j):
if j < min(sizes):
return (0, 'NoRoom')
else:
if j not in _knap:
_knap[j] = max((values[a]+knap(j-sizes[a])[0],f'Item {a}',j-sizes[a]) for a in range(3)
if j >= sizes[a])
return _knap[j]
# Memoization
_fib = {}
def fib(n):
if n <= 2:
return 1
else:
if n not in _fib:
_fib[n] = fib(n-1) + fib(n-2)
return _fib[n]