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
# 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.
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 and btl != 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)): bottles_picked.append(bottle) cap = cap % bottle 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 bottle_value = bottle_tuples if len(bottle_tuples) == 1: num_bottles = math.floor(capacity / bottle_weight) last_value = bottle_tuples * 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))