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:

```
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
```

CLICK HERE to find out more related problems solutions.