def knapsack(w,v,num,mw):
res=[[-1 for j in range(mw+1)] for i in range(num+1)]
for j in range(mw+1):
res[0][j]=0
for i in range(1,num+1):
for j in range(1,mw+1):
res[i][j]=res[i-1][j]
if j>=w[i-1] and res[i][j] < res[i-1][j-w[i-1]]+v[i-1]:
res[i][j]=res[i-1][j-w[i-1]]+v[i-1]
return res[num][mw]
w=[2,2,6,5,4]
v=[6,3,5,4,6]
print(knapsack(w,v,len(w),10))
What happens if you add an item?
def common_substring(s1,s2):
cell=[[] for x in range(len(s1))]
for x in cell:
for y in range(len(s2)):
x.append(0)
longest=0
for i in range(len(s1)):
for j in range(len(s2)):
if i==0 or j==0:
if s1[i]==s2[j]:
cell[i][j]=1
else:
if s1[i]==s2[j]:
cell[i][j]=cell[i-1][j-1]+1
if cell[i][j]>longest:
longest = cell[i][j]
return longest
def common_subsequence(s1,s2):
cell=[[] for x in range(len(s1))]
for x in cell:
for y in range(len(s2)):
x.append(0)
longest=0
for i in range(len(s1)):
for j in range(len(s2)):
if i==0 or j==0:
if s1[i]==s2[j]:
cell[i][j]=1
else:
if s1[i]==s2[j]:
cell[i][j]=cell[i-1][j-1]+1
else:
cell[i][j]=max(cell[i-1][j],cell[i][j-1])
if cell[i][j]>longest:
longest = cell[i][j]
return longest
# Recursive Version of Coin Optimization Problem
def recMC(coinValueList,change):
minCoins = change
if change in coinValueList:
return 1
else:
for i in [c for c in coinValueList if c <= change]:
numCoins = 1 + recMC(coinValueList,change-i)
if numCoins < minCoins:
minCoins = numCoins
return minCoins
print(recMC([1,5,10,25],63))
# DP solution
def dpMakeChange(coinValueList,change,minCoins):
for cents in range(change+1):
coinCount = cents
for j in [c for c in coinValueList if c <= cents]:
if minCoins[cents-j] + 1 < coinCount:
coinCount = minCoins[cents-j]+1
minCoins[cents] = coinCount
return minCoins[change]
print(dpMakeChange([1,5,10,25],63,{}))
# Modified DP solution
def dpMakeChange(coinValueList,change,minCoins):
for cents in range(change+1):
coinCount = cents
newCoin = 1
for j in [c for c in coinValueList if c <= cents]:
if minCoins[cents-j] + 1 < coinCount:
coinCount = minCoins[cents-j]+1
newCoin = j
minCoins[cents] = coinCount
coinsUsed[cents] = newCoin
return minCoins[change]
def printCoins(coinsUsed,change):
coin = change
while coin > 0:
thisCoin = coinsUsed[coin]
print(thisCoin)
coin = coin - thisCoin
coinsUsed={}
print(dpMakeChange([1,5,10,25],63,{}))
printCoins(coinsUsed, 63)