Fractional Knapsack (Greedy by Value Density)

• Fractional Knapsack – a variant of the knapsack problem where items may be taken in fractions, not just whole.
• Value density – the value-to-weight ratio value / weight measures how much return each unit of capacity delivers.
• Greedy strategy – sort items by density descending, take each whole while capacity remains, and take a fraction of the last item that only partly fits.
• Optimality proof – because partial selection is allowed, skipping a denser item in favour of a sparser one can never help, so a simple exchange argument proves the greedy is optimal.
• Complexity – O(n log n) for sorting, O(n) for the greedy scan, giving O(n log n) overall with O(1) extra space.

What is the Fractional Knapsack problem?

The Fractional Knapsack problem gives you a set of items, each with a weight and a value, and a knapsack with a fixed weight capacity. You must select items to maximise total value, and you are allowed to take any fraction of an item. The fraction taken earns a proportional share of that item's value. This is different from the 0/1 Knapsack where each item is either taken whole or left behind.

In banking terms, the National Bank of India has a capital pool (the capacity) and a list of investment opportunities (the items), each with a required investment amount (weight) and expected return (value). The bank can partially fund any opportunity, earning a proportional return.

Why does a greedy approach work here?

The greedy approach works because fractions are allowed. If you can take any portion of an item, there is never a reason to skip a high-density item in favour of a low-density one. You always benefit from filling capacity with the densest item first.

The formal argument is an exchange proof. Suppose an optimal solution skips some fraction of a denser item A in favour of a sparser item B. Swapping some capacity from B to A improves total value without violating the capacity constraint. Therefore the density-sorted greedy is optimal.

In the 0/1 version this argument fails because items are indivisible. A small dense item might leave leftover capacity that a larger but sparser item could have filled more valuably.

// Why greedy fails for 0/1 Knapsack
// Items: (weight=10, value=60), (weight=20, value=100), (weight=30, value=120)
// Capacity = 30
// Greedy by density takes item1 (ratio 6.0) + item2 (ratio 5.0) = 160
// But item1 + item3 is not possible (weight 40 > 30)
// Optimal 0/1: item2 + item1 = 160, but item3 alone = 120
// Greedy happens to work here, but consider:
// Items: (weight=10, value=60), (weight=20, value=100)
// Capacity = 20 -> greedy takes item1 (60), misses item2 (100)

How does the algorithm work step by step?

The algorithm has three phases: compute density, sort, and fill.

1. For each item, compute the value-to-weight ratio.
2. Sort items by ratio in descending order.
3. Walk through the sorted items. For each item, if the remaining capacity can hold it entirely, take it whole. Otherwise, take the fraction that fills the remaining capacity and stop.

package com.bank.service;

import java.math.BigDecimal;
import java.math.RoundingMode;
import java.util.Arrays;
import java.util.Comparator;

public class FractionalKnapsackService {

    public static BigDecimal maximiseReturn(
            BigDecimal[] investmentAmounts,
            BigDecimal[] expectedReturns,
            BigDecimal capitalPool) {

        int n = investmentAmounts.length;
        Integer[] indices = new Integer[n];
        for (int i = 0; i < n; i++) indices[i] = i;

        // Step 1 and 2: sort by return-per-unit descending
        Arrays.sort(indices, (a, b) -> {
            BigDecimal ratioA = expectedReturns[a].divide(investmentAmounts[a], 10, RoundingMode.HALF_UP);
            BigDecimal ratioB = expectedReturns[b].divide(investmentAmounts[b], 10, RoundingMode.HALF_UP);
            return ratioB.compareTo(ratioA);
        });

        BigDecimal totalReturn = BigDecimal.ZERO;
        BigDecimal remaining = capitalPool;

        // Step 3: greedy fill
        for (int idx : indices) {
            if (remaining.compareTo(BigDecimal.ZERO) <= 0) break;

            if (remaining.compareTo(investmentAmounts[idx]) >= 0) {
                // Take the whole investment
                remaining = remaining.subtract(investmentAmounts[idx]);
                totalReturn = totalReturn.add(expectedReturns[idx]);
            } else {
                // Take a fraction of the investment
                BigDecimal fraction = remaining.divide(investmentAmounts[idx], 10, RoundingMode.HALF_UP);
                totalReturn = totalReturn.add(expectedReturns[idx].multiply(fraction));
                remaining = BigDecimal.ZERO;
            }
        }
        return totalReturn.setScale(2, RoundingMode.HALF_UP);
    }
}

How is Fractional Knapsack different from 0/1 Knapsack?

| Aspect | Fractional Knapsack | 0/1 Knapsack |
|---|---|---|
| Item selection | Can take any fraction 0.0 to 1.0 | Must take whole or leave |
| Algorithm | Greedy by density | Dynamic programming |
| Optimality of greedy | Provably optimal | Greedy can be suboptimal |
| Time complexity | O(n log n) | O(n * W) pseudo-polynomial |
| Space complexity | O(1) extra | O(n * W) or O(W) optimised |
| Use case | Partial investment funding | Indivisible item selection |

// 0/1 Knapsack requires DP
public static int zeroOneKnapsack(int[] weights, int[] values, int capacity) {
    int n = weights.length;
    int[] dp = new int[capacity + 1];
    for (int i = 0; i < n; i++) {
        for (int w = capacity; w >= weights[i]; w--) {
            dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
        }
    }
    return dp[capacity];
}

What are the edge cases?

Edge cases require careful handling to avoid division errors and incorrect results.

• Capacity is zero – no items can be taken, return zero.
• All items fit – take everything whole, no fraction needed.
• Single item larger than capacity – take only the fraction that fits.
• Items with zero weight – would cause division by zero when computing density. Filter these out and add their value for free.
• All items have equal density – order does not matter, fill arbitrarily.

// Edge case: item with zero weight gives free value
if (investmentAmounts[idx].compareTo(BigDecimal.ZERO) == 0) {
    totalReturn = totalReturn.add(expectedReturns[idx]);
    continue;
}

What are the common mistakes?

The most frequent mistake is sorting by value alone instead of by value-to-weight ratio.

// WRONG: sorting by value descending
Arrays.sort(indices, (a, b) -> expectedReturns[b].compareTo(expectedReturns[a]));
// This picks the highest-value item first, but it might consume
// too much capacity for its return per unit.

// CORRECT: sorting by value-to-weight ratio descending
Arrays.sort(indices, (a, b) -> {
    BigDecimal ratioA = expectedReturns[a].divide(investmentAmounts[a], 10, RoundingMode.HALF_UP);
    BigDecimal ratioB = expectedReturns[b].divide(investmentAmounts[b], 10, RoundingMode.HALF_UP);
    return ratioB.compareTo(ratioA);
});

Another mistake is forgetting to break after taking a fraction. Once the remaining capacity hits zero, no more items can be added.

What is the time and space complexity?

The dominant cost is the sort, which runs in O(n log n). The greedy scan after sorting is a single O(n) pass. No auxiliary data structure scales with input size beyond the index array, so extra space is O(n) for the index array or O(1) if sorting items in place.

In a banking portfolio service handling thousands of investment opportunities, the n log n sort is fast enough to run in real time. For millions of items, a partial sort selecting the top-k densest items could bring the cost even lower when the knapsack fills after only a few items.

javac com/bank/service/FractionalKnapsackService.java
java com.bank.service.FractionalKnapsackService

Maximum return with capital pool 50: 240.00

When should you use Fractional Knapsack?

Use Fractional Knapsack when items are divisible and partial allocation is meaningful. In banking, this applies to capital allocation across partially fundable investments, distributing a fixed marketing budget across campaigns that accept any funding level, and splitting available liquidity across loan disbursements.

Do not use it when items are indivisible. Hiring decisions (you cannot hire half a person), server provisioning (you cannot provision half a machine), and selecting whole loan applications for approval are all 0/1 knapsack problems that require dynamic programming.

What should a senior engineer know?

A senior engineer should be able to prove the greedy is optimal using an exchange argument. The proof states: if any optimal solution does not follow the density order, swapping capacity from a less dense item to a more dense one strictly improves the total value without exceeding capacity, contradicting the assumption that the original was optimal.

Senior engineers should also know that the fractional knapsack is a special case of linear programming. The LP relaxation of the integer 0/1 knapsack is exactly the fractional knapsack, which is why LP solvers use it as a bound in branch-and-bound algorithms for the integer version.

// Exchange argument in pseudocode
// Suppose optimal O uses fraction f_A < 1 of item A (denser)
// and fraction f_B > 0 of item B (sparser)
// Transfer delta capacity from B to A:
//   new value = old value - delta*(vB/wB) + delta*(vA/wA)
//   Since vA/wA > vB/wB, the new value > old value
//   Contradiction: O was not optimal

What are common interview follow-up questions?

Interviewers often ask these follow-ups after the fractional knapsack:

• What if items are indivisible? Then use 0/1 knapsack with DP.
• What if you can take unlimited copies? Then use unbounded knapsack DP.
• Can you solve it without sorting? A partial sort or quickselect on the pivot density can work if the knapsack fills with very few items.
• What is the relationship to linear programming? The fractional knapsack is the LP relaxation of the 0/1 integer program.