#### unbounded knapsack: similar to 01 knapsack but we can choose infinite number of items
#### example w=[2 3 4], value=[100,50,10],; in 01 knapsack, w=2 can be picked one time,
#### but in unbounded, we can pick multiple times.
def unboundKS(C,w,v):
    m=len(w)
    L=[[0]*(C+1) for x in range(0,m+1)] ## due to the base case get the first row and column, then the matrix size should be +1 compare with the real data is C and m

    for i in range(0,m+1):
        for j in range(0,C+1):
            ### base cases:
            if i==0 or j==0:
                L[i][j]=0
            if w[i-1]>j:
                L[i][j]=L[i-1][j]
            else:
                k=j//w[i-1]
                maximum=0
                for q in range(0,k+1):
                    maximum=max(q*v[i-1]+L[i-1][j-q*w[i-1]],maximum) ## scan all posible of q which is the number of item [i-1]th be picked
                L[i][j]=maximum
    return L[m][C]
C=100
v=[10,30,20]
w=[5,10,15]
print(unboundKS(C,w,v))