Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Linear programming solution in Clear category for Treasures by Oleg_Domokeev
def treasures(info, limit):
# To consider all possible cases, even exotic (small differences in prices per gram and relatively great difference in weight
# and so on), I think that we need to find the maximal cost trough the all variants of (n0, n1, n2) that lay on or just under
# flatness: sum(wi*ni)=limit*1000 where index i is used for each type of treasure, w - weight, n - number of items
# if any n is integer and does not exceed the maximal amount in the vault
p0, w0, a0 = info['golden coin']['price'], info['golden coin']['weight'], info['golden coin']['amount']
p1, w1, a1 = info['silver coin']['price'], info['silver coin']['weight'], info['silver coin']['amount']
p2, w2, a2 = info['ruby']['price'], info['ruby']['weight'], info['ruby']['amount']
items = ['golden coin', 'silver coin', 'ruby']
l = int(limit * 1000)
# consider the unique variant
if w0 * a0 + w1 * a1 + w2 * a2 <= l:
res = (a0, a1, a2)
# for common case
else:
# here I use generator to find all variants described above. The number of variat is great, therefore I haven't used list.
extrem = ((i, j, (l-i*w0-j*w1)//w2) for i in range(min(l//w0, a0)+1) for j in range(min((l-i*w0)//w1, a1)+1)
if (l-i*w0-j*w1)//w2 <= a2)
# find maximum cost through extrem
max_cost = 0
for point in extrem:
cost = point[0]*p0+point[1]*p1+point[2]*p2
if cost > max_cost:
max_cost, res = cost, point
return [items[i] + ': ' + str(res[i]) for i in range(3) if res[i]]
Sept. 18, 2018
Comments:
