Same here. I think the time limit of that problem needs to be adjusted. My solution for the limit case runs in 0.8s:
start_time = time()
print(get_worst_case(9999,[(randrange(1,50000),randrange(1,10000)) for _ in range(500)]))
print(time()-start_time)
My Solution
def get_worst_case(weight, avail_coins):
'''
get worst case scenario for the pigbank
:param weight: total weight to match
:param avail_coins: list of tuple [(coin value, coin weight)]
:return: worst case value
'''
max_value = max(map(lambda c: c[0], avail_coins))
impossible = 1+max_value*weight
partial = [0 for _ in range(weight+1)]
for p_w in range(1,len(partial)):
min_value = impossible
for c_v,c_w in avail_coins:
if p_w - c_w >= 0:
p_v_with_c = partial[p_w - c_w] + c_v
if p_v_with_c < min_value:
min_value = p_v_with_c
partial[p_w] = min_value
return partial[-1] if partial[-1] != impossible else None
cases = int(input())
for c in range(cases):
ef = input().split(" ")
e = int(ef[0])
f = int(ef[1])
weight = f-e
num_coins = int(input())
avail_coins = []
for coin in range(num_coins):
pw = input().split(" ")
avail_coins.append((int(pw[0]),int(pw[1])))
worst_value = get_worst_case(weight,avail_coins)
if worst_value == None:
print("This is impossible.")
else:
print("The minimum amount of money in the piggy-bank is "+str(worst_value)+"."