Crack the Backend

Problem Statement

You have n items: item i has weight weights[i] and value values[i]. The knapsack has capacity W. You may take any fraction of each item (e.g. half of an item gives half its value and uses half its weight). Return the maximum total value you can carry.

Key Observations

Greedy: Sort items by value per unit weight (value/weight) descending. Always take as much as possible of the item with the highest ratio first; when that item is exhausted (or capacity filled), move to the next. This is optimal because if we ever leave a fraction of a higher-ratio item to take a lower-ratio one, swapping would increase value.

Approach

High-level: Sort by value/weight descending. For each item: take amount = min(weight, remaining W), add amount * (value/weight) to total, W -= amount; if W == 0 break. Return total.

Steps: Build pairs (value, weight), sort by value/weight. double total = 0, cap = W; for each: take = min(w, cap), total += take * (v/w), cap -= take; if cap==0 break. return total.

Implementation

Java

public double fractionalKnapsack(int W, int[] values, int[] weights) {
    int n = values.length;
    double[][] arr = new double[n][3];

    for (int i = 0; i < n; i++) { arr[i][0] = values[i]; arr[i][1] = weights[i]; arr[i][2] = (double)values[i]/weights[i]; }
    Arrays.sort(arr, (a,b) -> Double.compare(b[2], a[2]));
    double val = 0;

    for (int i = 0; i < n && W > 0; i++) {
        double take = Math.min(W, arr[i][1]);
        val += take * arr[i][2];
        W -= take;
    }

    return val;
}

Test Cases

Example

Input

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

Expected

240

Explanation

Take all of 1 and 2, 2/3 of 3.

Complexity Analysis

Time: typically O(n) or O(n log n).
Space: O(1) or O(n).

Follow-ups

Prove greedy choice property; handle ties.