Class FractionalKnapsack

java.lang.Object

topics.greedy.knapsack.FractionalKnapsack

public class FractionalKnapsack
extends Object

Fractional Knapsack

Evaluates a set of items, each with a specific weight and value, to determine the combination that maximizes the total value within a knapsack's weight limit. Crucially, items can be broken into fractions if they don't fit entirely.

The Greedy Choice

Because items can be fractionalized, the mathematically optimal strategy is to:

1. Calculate the Value-to-Weight ratio for each item.
2. Sort items descending by this ratio.
3. Take as much of the highest-ratio items as possible until the knapsack is full.

This Guarantees the global optimum, unlike the 0/1 Knapsack variant which requires Dynamic Programming.

• Time Complexity: O(N log N) - Bound by the sorting step.
• Space Complexity: O(N) - To store the fractional solution and helper objects.

Author:

vicegd

Constructor Summary

Constructors

Constructor	Description
FractionalKnapsack()

Method Summary

Modifier and Type	Method	Description
float[]	fillKnapsack(int maxWeight, int[] weights, int[] values)	Calculates the optimal fractional distribution of items to maximize value.

Methods inherited from class Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

FractionalKnapsack

public FractionalKnapsack()

Method Details

fillKnapsack

public float[] fillKnapsack(int maxWeight,
 int[] weights,
 int[] values)

Calculates the optimal fractional distribution of items to maximize value.

Parameters:

maxWeight - The maximum weight capacity of the knapsack.

weights - The absolute weight of each item.

values - The absolute value of each item.

Returns:

A float array representing the fraction taken of each item (0.0 to 1.0).