Water Bottle Sample Day

Mar 5, 2020


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(2), reverse=True)

    bottles_picked = []
    cap = capacity
    for bottle in annotated_list:
        for _ in range(int(cap / bottle[0])):
        cap = cap % bottle[0]
        if cap == 0:

    # 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))