| Step | Target Item | Capacity Check | Fractional Slice Selection Allocation |
|---|
The Fractional Strategy & Value-to-Weight Optimization
Unlike the rigid 0/1 variant, the Fractional Knapsack problem operates under a continuous optimization framework. Given a set of n items with distinct values vi and weights wi, the algorithm is permitted to accept arbitrary fractions xi (where 0 ≤ xi ≤ 1) of any available item. This freedom to divide items transforms the structural layout from an NP-hard problem into an elegant global density maximization challenge that can be solved perfectly using a greedy paradigm.
To execute this, the algorithm calculates the critical unit worth or cost-benefit index for each item. The system then processes items in decreasing order of this value-to-weight ratio to maximize immediate returns.
Ri = vi / wi (Value per Unit Weight)
Global Sorting Vector:
R1 ≥ R2 ≥ R3 ≥ ... ≥ Rn
Greedy Selection & Fractional Apportionment Mechanics
The computational engine loops through the sorted list of item objects and makes choices using a deterministic local strategy:
- Complete Absorption: If the current item's total mass is less than or equal to the knapsack's remaining residual capacity, the item is swallowed completely (xi = 1). The item's entire weight is subtracted from the capacity, and its full value is accrued.
- Fractional Splitting: When an item is encountered that exceeds the remaining volume, the greedy mechanism splits the item. It calculates the precise fraction needed to hit exactly 100% capacity utilization. The remaining space is filled, the maximum profit is compounded, and the loop terminates.
Asymptotic Complexity & Proof of Correctness
This greedy approach yields absolute mathematical optimality because prioritizing the highest value densities ensures maximum value accumulation per unit of weight at every step. The time complexity of this workflow is bounded completely by the sorting phase, yielding an O(n · log n) profile, while the selection pass itself takes linear O(n) time. The auxiliary space requirement settles into an efficient O(1) or O(n) profile depending on the sorting implementation, avoiding memory-expensive tracking arrays altogether.