Knapsack without repetitions: Maximum Amount of Gold – Python code question

I implemented my own solution using array of bools `d`, element `d[i][j]` is `True` if and only if weight `j` can be composed in some way by taking/not-taking golds with indexes `0` to `i`. We start from row that contains `True` only for `j = 0` i.e. weight `0` can be composed by not taking anything. Each next row is computed as follows – element `d[i][j]` is True if `d[i - 1][j]` is True (which corresponds to not taking current gold) or if `d[i - 1][j - golds[i]]` is True (which corresponds to taking current gold).

Regarding your solution. I’ll suggest to do next correction in your algorithm, keys of dict `gold_dict` should have second element equal to index of gold bar, not the value of gold bar, i.e. instead of `gold_dict[(weight, gold[i])]` you need to use everywhere `gold_dict[(weight, i)]`, try doing this correction and maybe your code will work for all tests! Your corrected with this suggestion code is here.

My solution code is down below:

Try it online!

``````def optimal_weight(W, golds):
# We can compose weight 0 by taking nothing
d = [[True] + [False] * W]
for i in range(len(golds)):
# We copy previous row which corresponds to
# solution of not taking current gold
d.append(d[-1][:])
for w in range(golds[i], W + 1):
# Weight w can be composed either by not taking current
# gold (d[-2][w]) or by taking it (d[-2][w - golds[i]])
d[-1][w] = d[-2][w] or d[-2][w - golds[i]]
# It is enough to keep only last row
d = d[-1:]
for w in range(W, -1, -1):
# Return maximal weight w that has True in d
if d[-1][w]:
return w

if __name__ == '__main__':
import sys
W, n, *w = list(map(int, sys.stdin.read().split()))
print(optimal_weight(W, w))
``````

Input:

``````10 3
1 4 8
``````

Output:

``````9
``````