# input: v[0..N) and w[0..N) arrays of natural numbers, N>=0, and C>=0## output: Maximum retribution by choosing elements with individual# retribution and weight in v[0..N) and w[0..N), respectively,# to carry in a knapsack with weight capacity C## O(NC) time and space solutiondefks_tab(v,w,C):N=len(v)tab=[[0forcinrange(C+1)]forninrange(N+1)]n,c=1,0whilen!=N+1:ifc==C+1:n,c=n+1,0else:tab[n][c]=tab[n-1][c]ifw[n-1]<=c:tab[n][c]=max(tab[n][c],v[n-1]+tab[n-1][c-w[n-1]])c+=1returntab[N][C]
Comments (0)
HTTPSSSH
You can clone a snippet to your computer for local editing.
Learn more.