I implemented my own solution using array of bools
True if and only if weight
j can be composed in some way by taking/not-taking golds with indexes
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))
10 3 1 4 8
CLICK HERE to find out more related problems solutions.