Fractional Knapsack

Problem Statement

Given weights and values of items and a knapsack capacity, maximize value by taking fractions of items. This medium-level greedy problem is about optimization—fill your bag with the most valuable pieces!

Example

Input: values = [60, 100, 120], weights = [10, 20, 30], W = 50

Output: 240 (all of [60,10], all of [100,20], 2/3 of [120,30])

Input: values = [60, 100], weights = [10, 20], W = 25

Output: 140

Code

public class Solution {
    public double fractionalKnapsack(int[] values, int[] weights, int W) {
        int n = values.length;
        double[][] items = new double[n][2];
        for (int i = 0; i < n; i++) {
            items[i][0] = values[i] / (double) weights[i];
            items[i][1] = weights[i];
        }
        Arrays.sort(items, (a, b) -> Double.compare(b[0], a[0]));
        double totalValue = 0;
        int currWeight = 0;
        for (int i = 0; i < n && currWeight < W; i++) {
            if (currWeight + items[i][1] <= W) {
                currWeight += items[i][1];
                totalValue += items[i][0] * items[i][1];
            } else {
                double fraction = (W - currWeight) / items[i][1];
                totalValue += fraction * items[i][0] * items[i][1];
                break;
            }
        }
        return totalValue;
    }
}
            

def fractional_knapsack(values, weights, W):
    items = sorted([(v/w, w) for v, w in zip(values, weights)], reverse=True)
    total_value = 0
    curr_weight = 0
    for value_per_weight, weight in items:
        if curr_weight + weight <= W:
            curr_weight += weight
            total_value += value_per_weight * weight
        else:
            fraction = (W - curr_weight) / weight
            total_value += fraction * value_per_weight * weight
            break
    return total_value
            

function fractionalKnapsack(values, weights, W) {
    let items = values.map((v, i) => [v / weights[i], weights[i]]);
    items.sort((a, b) => b[0] - a[0]);
    let totalValue = 0, currWeight = 0;
    for (let [valuePerWeight, weight] of items) {
        if (currWeight + weight <= W) {
            currWeight += weight;
            totalValue += valuePerWeight * weight;
        } else {
            let fraction = (W - currWeight) / weight;
            totalValue += fraction * valuePerWeight * weight;
            break;
        }
    }
    return totalValue;
}
            

Explanation

• Greedy Choice: Sort by value/weight, take highest value items first.
• Flow: Take full items or fractions to fill capacity.
• Example: [60/10,100/20,120/30] → 6,5,4; take 10, 20, 20/30 of last.

Note