ChiPy Algorithms SIGDescription
A new and upcoming water bottle supplier is having an ‘unlimited samples day’ of their product where you as a store owner and buyer will be able to take any combination of water bottles with you as long as it all fits in a duffel bag the supplier provides you. This duffel bag can hold limited weight and you want to make off with the most valuable haul possible.
While the supplier has a limited number of types of water bottles, they do have an unlimited supply of each type. Each type of water bottle has a weight and a value, stored in a tuple with two indices:
0. An integer representing the weight of the water bottle in ounces.
1. An integer represeting the monetary value of the water bottle in USD
For example:
# Weighs 13 ounces and has a value of $50
(13, 50)
Write a function max_duffel_bag_value() that takes a list of water bottle type tuples and a weight capacity and returns the maximum monetary value the duffel bag can hold.
For example:
bottle_tuples = [(7, 160), (3, 90), (2, 15)]
capacity = 20
max_duffel_bag_value(bottle_tuples, capacity)
# Returns 555 (6 of the middle type of bottle and 1 of the last type of bottle)
Weights and values may be any non-negative integer. Yes, it is weird to think about water bottles that weigh nothing or duffel bags that can not hold anything. But we are not just super mastermind criminals — we are also meticulous about keeping our algorithms flexible and comprehensive.
Solution by adambain
Note this is an implementation of the greedy algorithm sorted by ratio (value/weight), for this problem, the greedy algorithm may not return the optimal solution. -Adam
def water_bottle(list, capacity):
for btl in list:
if btl[0] == 0 and btl[1] != 0:
return float('inf')
if capacity == 0:
return 0
annotated_list = [(weight, price, price/weight) for (weight, price) in list]
annotated_list.sort(key=itemgetter(0))
annotated_list.sort(key=itemgetter(2), reverse=True)
bottles_picked = []
cap = capacity
for bottle in annotated_list:
for _ in range(int(cap / bottle[0])):
bottles_picked.append(bottle)
cap = cap % bottle[0]
if cap == 0:
break
# uncomment to see the selected bottles
# print("picked bottles :", bottles_picked)
return sum([price for (weight, price, ratio) in bottles_picked])
Recursive Solution by cgundy
def max_duffel_bag_value_helper(bottle_tuples, capacity, total_value):
if len(bottle_tuples) == 0:
return 0
if capacity == 0:
return 0
bottle_weight = bottle_tuples[0][0]
bottle_value = bottle_tuples[0][1]
if len(bottle_tuples) == 1:
num_bottles = math.floor(capacity / bottle_weight)
last_value = bottle_tuples[0][1] * num_bottles
return total_value + last_value
if capacity - bottle_weight <= 0:
return total_value
return max(max_duffel_bag_value_helper(bottle_tuples, capacity-bottle_weight, total_value+bottle_value),
max_duffel_bag_value_helper(bottle_tuples[1:], capacity-bottle_weight, total_value+bottle_value))
def max_duffel_bag_value(bottle_tuples, capacity):
total_value = 0
return max(max_duffel_bag_value_helper(bottle_tuples, capacity, total_value),
max_duffel_bag_value_helper(bottle_tuples[1:], capacity, total_value))