function knapsack(k:integer):integer；
begin
knapsack:=0；
for i:=1 to n do
if k-w[i]>=0 then
begin
t:=knapsack(k-w[i])+v[i]；
if knapsack < t then knapsack:=t；
end;
end；
class calc:
def __init__(self):
self.n = random.randint(5, 20)
self.v = [random.randint(1, 100) for i in range(self.n)]
self.w = [random.randint(1, 100) for i in range(self.n)]
self.state = {}
return
def calc_k(self, k):
r = [0,[]]
for i in range(self.n):
k1 = k - self.w[i]
if k1 >= 0:
t,p = self.state.get(k1)
t = t+self.v[i]
if r[0]<t:
r = [t, p+[i,]]
self.state[k] = r
return r
def main(self,m,n,w,v):
self.n,self.w,self.v = n,w[:],v[:]
self.state.clear()
r = None
for i in range(m+1):
r = self.calc_k(i)
return r