We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Price to Fill a Bag

Number: 2693

Difficulty: Medium

Paid? Yes

Companies: Microsoft

Problem Description

Given a list of items where each item has a price and a weight, you need to exactly fill a bag with a specified capacity. You may take an entire item or split an item into two parts (each item can be split at most once) so that the two pieces add up to the full item. The price and weight of a fractional piece are proportional to the ratio taken. If it is impossible to exactly reach the bag’s capacity (i.e. the sum of weights of all items is less than the capacity), return -1. Otherwise, return the maximum total price that can be achieved. Answers within 10⁻⁵ of the correct answer will be accepted.

Key Insights

  • This is essentially a fractional knapsack problem with the twist that every item can be split at most once.
  • The maximum capacity is exactly filled; if the total available weight (by taking full items or fractions) is less than the bag’s capacity, then it is impossible.
  • Use a greedy strategy: sort items by their price-to-weight ratio (value density) in descending order.
  • Add full items as long as they do not exceed the remaining capacity; when the next item is too heavy, take the exact fraction needed to fill the bag.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting. Space Complexity: O(n) (depending on the sorting algorithm and storage of items).

Solution

The problem is approached by first verifying that the sum of all weights is at least the capacity; otherwise, it is impossible to fill the bag and we output -1. Then, sort the items by their price per weight ratio in descending order. Iterate through the sorted list, and for each item, if its full weight can be added without exceeding the remaining capacity, add its full price. If the next item’s weight is more than the remaining capacity, take only the fraction of that item that exactly fills the capacity (this is the only split needed for that item). By using the greedy fractional knapsack approach, we ensure the maximum total price is obtained.

Code Solutions

# Python implementation for "Maximum Price to Fill a Bag"
def maximumPrice(items, capacity):
    # Calculate the total available weight from all items
    total_weight = sum(weight for _, weight in items)
    # If total weight is less than the required capacity, it's impossible to fill the bag
    if total_weight < capacity:
        return -1.0

    # Sort items based on their price-to-weight ratio in descending order
    items.sort(key=lambda item: item[0] / item[1], reverse=True)

    max_price = 0.0  # Holds the total maximum price
    remaining_capacity = capacity  # Remaining weight capacity of the bag

    # Iterate over each item in sorted order
    for price, weight in items:
        # If the current full item can fit into the remaining capacity
        if weight <= remaining_capacity:
            max_price += price  # take the full item
            remaining_capacity -= weight  # reduce the capacity
        else:
            # Take only the fraction of the item to fill the bag exactly
            fraction = remaining_capacity / weight
            max_price += price * fraction
            remaining_capacity = 0  # bag is now full
            break  # no more capacity remains

    return max_price

# Example usage:
if __name__ == "__main__":
    # Example 1
    items1 = [[50, 1], [10, 8]]
    capacity1 = 5
    print("{:.5f}".format(maximumPrice(items1, capacity1)))  # Expected output: 55.00000

    # Example 2
    items2 = [[100, 30]]
    capacity2 = 50
    print("{:.5f}".format(maximumPrice(items2, capacity2)))  # Expected output: -1.00000
← Back to All Questions