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