Created
August 9, 2018 02:18
-
-
Save kangeugine/8089406983584a53c6ec7d05ff3ed597 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
def knapSack(W, wt, val, n): | |
K = [[0 for x in range(W+1)] for x in range(n+1)] | |
for i in range(n+1): | |
for w in range(W+1): | |
if i==0 or w==0: | |
K[i][w] = 0 | |
elif wt[i-1] <= w: | |
K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w]) | |
else: | |
K[i][w] = K[i-1][w] | |
return K | |
def knapSackIndex(W, wt, val, n, K): | |
res = K[-1][-1] | |
ix = [] | |
w = W | |
ix = [] | |
for i in range(n, 0, -1): | |
if res <= 0: | |
break | |
if res == K[i - 1][w]: | |
continue | |
else: | |
ix.append(i-1) | |
res = res - val[i - 1] | |
w = w - wt[i - 1] | |
return ix |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment