Maximum Price to Fill a Bag - Practice Coding Problems

Maximum Price to Fill a Bag - Problem

You are given a 2D integer array items where items[i] = [price_i, weight_i] denotes the price and weight of the i^th item, respectively.

You are also given a positive integer capacity.

Each item can be divided into two items with ratios part1 and part2, where part1 + part2 == 1.

The weight of the first item is weight_i * part1 and the price of the first item is price_i * part1. Similarly, the weight of the second item is weight_i * part2 and the price of the second item is price_i * part2.

Return the maximum total price to fill a bag of capacity capacity with given items. If it is impossible to fill a bag return -1. Answers within 10^-5 of the actual answer will be considered accepted.

Input & Output

Example 1 — Basic Fractional Knapsack

$ Input: items = [[60,10],[100,20],[120,30]], capacity = 50

› Output: 240.0

💡 Note: Take full Item1 (60, 10kg), full Item2 (100, 20kg), and 2/3 of Item3 (80, 20kg). Total: 240 price, 50kg weight.

Example 2 — Exact Fit with Full Items

$ Input: items = [[10,5],[40,4],[30,6],[50,3]], capacity = 10

› Output: 90.0

💡 Note: Items sorted by ratio: [50,3]=16.67, [10,5]=2.0, [40,4]=10.0, [30,6]=5.0. Take [50,3] and [40,4] for total 90 price, 7kg weight. Need 3kg more - take 3/5 of [30,6] = 18 price. Total: 50+40+18=108 won't work. Take [50,3] full + 7/4 of [40,4] = 50 + 70 = 120 won't work. Actually take [50,3] + [40,4] + partial [10,5] = 50 + 40 + 0 = 90.

Example 3 — Impossible Case

$ Input: items = [[10,20],[20,30]], capacity = 10

› Output: -1

💡 Note: No item can fit in capacity 10 since minimum weight is 20. Return -1.

Constraints

1 ≤ items.length ≤ 1000
items[i].length == 2
1 ≤ price_i, weight_i ≤ 1000
1 ≤ capacity ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Input

Items with [price, weight] and target capacity

Process

Sort by price/weight ratio, take greedily with fractions

Output

Maximum price that exactly fills capacity or -1 if impossible

Key Takeaway

🎯 Key Insight: Sort items by price-to-weight ratio and greedily select the most efficient items, using fractional amounts to exactly fill the capacity

Asked in

G Google 15 a Amazon 12 M Microsoft 8

This is a fractional knapsack problem where items can be split. The key insight is to use a greedy approach: sort items by price-to-weight ratio and take the most efficient items first. The challenge is that we must fill the bag to exactly the given capacity. Best approach is greedy selection with fractional filling. Time: O(n log n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Combinations	O(2ⁿ)	O(n)	Try all possible fractional combinations of items to find maximum price
Greedy by Price-to-Weight Ratio	O(n log n)	O(n)	Sort items by price-to-weight ratio and greedily select the most efficient items first

Brute Force - Try All Combinations — Algorithm Steps

Generate all possible fractional splits for each item
Try every combination of fractional items
Check if total weight <= capacity
Track maximum price achieved

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Splits

Create all possible fractional combinations

Check Each

Verify weight constraint for each combination

Find Maximum

Track highest price that exactly fills capacity

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

double maxPrice = 0.0;

void backtrack(int items[][2], int n, int index, double currentWeight, double currentPrice, int capacity) {
    if (index == n) {
        if (fabs(currentWeight - capacity) < 1e-9) {
            if (currentPrice > maxPrice) {
                maxPrice = currentPrice;
            }
        }
        return;
    }
    
    int price = items[index][0];
    int weight = items[index][1];
    if (weight == 0) {
        backtrack(items, n, index + 1, currentWeight, currentPrice, capacity);
        return;
    }
    
    double fractions[] = {0, 0.25, 0.5, 0.75, 1.0};
    for (int i = 0; i < 5; i++) {
        double fraction = fractions[i];
        double newWeight = currentWeight + weight * fraction;
        if (newWeight <= capacity + 1e-9) {
            double newPrice = currentPrice + price * fraction;
            backtrack(items, n, index + 1, newWeight, newPrice, capacity);
        }
    }
}

double solution(int items[][2], int n, int capacity) {
    if (n == 0 || capacity <= 0) {
        return -1.0;
    }
    
    maxPrice = 0.0;
    backtrack(items, n, 0, 0.0, 0.0, capacity);
    return maxPrice > 0 ? maxPrice : -1.0;
}

int main() {
    // Simplified input parsing for this example
    int items[100][2];
    int n = 0;
    int capacity;
    
    // In practice, would parse JSON format properly
    scanf("%d", &capacity);
    
    double result = solution(items, n, capacity);
    printf("%f\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2ⁿ)

Exponential combinations of fractional item splits

✓ Linear Growth

Space Complexity

O(n)

Storage for tracking current combination

⚡ Linearithmic Space

12.8K Views

Medium Frequency

~15 min Avg. Time

425 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Combinations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler