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.