Fractional Knapsack Visualizer
3px
Greedy Algorithms Optimization Greedy Choice

Fractional Knapsack Visualizer

Solve the fractional knapsack problem using a greedy algorithm. Select items by their value-to-weight ratio to maximize total value within a weight capacity.

Theory

The fractional knapsack problem allows items to be divided into fractional parts. The greedy strategy sorts items by value-to-weight ratio in descending order, then fills the knapsack by selecting items with highest ratio first. This greedy choice always yields the optimal solution for this variant.

  • Strategy: Sort by value/weight ratio (descending), greedily pick items until knapsack is full
  • Time Complexity: O(n log n) due to sorting; selection is O(n)
  • Space Complexity: O(n) for storing items and ratios
  • Key Property: Greedy choice property holds: best ratio item is always optimal to pick first
  • Common Applications:
    • Resource allocation with partial assignments
    • Portfolio optimization (fractional assets)
    • Load balancing with flexible tasks
    • Media transmission with partial files

Problem Statement

Given an array items where items[i] = [weighti, valuei], and an integer capacity representing maximum weight the knapsack can hold, return the maximum total value you can place in the knapsack.

You may take an item fully or take any fraction of it. The value gained from a fraction is proportional to the fraction taken.

Required Output: A floating-point number representing the maximum achievable value.

Example 1:

Input: items = [[10,60],[20,100],[30,120]], capacity = 50
Output: 240.00
Explanation:
- Ratios: 6.0, 5.0, 4.0
- Take item [10,60] fully, item [20,100] fully
- Remaining capacity = 20, take 20/30 of [30,120] = 80
- Total = 60 + 100 + 80 = 240

Example 2:

Input: items = [[5,30],[10,40],[20,100]], capacity = 15
Output: 80.00
Explanation:
- Ratios: 6.0, 4.0, 5.0 -> sorted as [5,30], [20,100], [10,40]
- Take [5,30] fully
- Remaining capacity = 10, take 10/20 of [20,100] = 50
- Total = 30 + 50 = 80.00

Constraints:

  • 1 ≤ items.length ≤ 105
  • 1 ≤ weighti, valuei ≤ 104
  • 1 ≤ capacity ≤ 109
  • Answer accepted within 1e-5 absolute error.

greedy_strategy.txt

1// Greedy Strategy
2struct Item {
3double weight, value;
4double ratio; // value/weight
5}
6
7// 1. Compute value/weight ratio for each item
8// 2. Sort items by ratio (descending)
9// 3. Fill knapsack greedily
10// 4. If item fits fully, take all
11// 5. Else take fraction that fits

ratio_anatomy.svg

Item A 5.0 Item B 3.2 Item C 1.5 Knapsack (Capacity) Fill greedily by ratio

knapsack.svg — Fractional Knapsack Visualization

Selected (Full)
Partial
Available
Ready to solve

Selection State

items.log

Item Weight Value Ratio Status

result.log

Total Value & Weight

Value: 0.0 | Weight: 0.0

Step Info

Waiting to solve...

Algorithm & Pseudocode

fractional_knapsack.txt

1// Greedy Fractional Knapsack
2function fractionalKnapsack(items, capacity):
3// Compute ratio for each item
4for item in items:
5item.ratio = item.value / item.weight
6
7// Sort by ratio (descending)
8sort(items by ratio, descending)
9
10totalValue = 0, usedCapacity = 0
11for item in items:
12if usedCapacity + item.weight ≤ capacity:
13totalValue += item.value
14usedCapacity += item.weight
15else:
16fraction = (capacity - usedCapacity) / item.weight
17totalValue += item.value * fraction
18break
19return totalValue

complexity.md

AspectComplexity
TimeO(n log n)
SpaceO(n)
Greedy ChoiceMax Ratio

Implementation

fractional_knapsack.c

1#include <stdio.h>
2#include <stdlib.h>
3typedef struct {
4double weight, value;
5} Item;
6int compare(const void *a, const void *b) {
7double r1 = ((Item *)a)->value / ((Item *)a)->weight;
8double r2 = ((Item *)b)->value / ((Item *)b)->weight;
9return r2 > r1 ? 1 : -1;
10}
11double fractionalKnapsack(Item items[], int n, double capacity) {
12qsort(items, n, sizeof(Item), compare);
13double totalValue = 0.0;
14for (int i = 0; i < n; i++) {
15if (capacity >= items[i].weight) {
16capacity -= items[i].weight;
17totalValue += items[i].value;
18} else {
19totalValue += items[i].value * (capacity / items[i].weight);
20break;
21}
22}
23return totalValue;
24}

Explanation

typedef struct: Defines Item structure holding weight and value as doubles for fractional calculations.

compare(): Comparator for qsort computes value/weight ratio on-the-fly for each item pair, returns 1 or -1 to sort descending by ratio. Essential for greedy selection.

qsort(): Standard library function performs sorting in O(n log n) time. Pass items array, count, size of each element, and comparator function pointer.

Main Loop: Iterates through sorted items in order of best ratio. If item fits fully, add entire value; else calculate fractional part and break (greedy fill).

Fractional Calculation: Line 19 computes (remaining_capacity / item_weight) * item_value—the maximum value achievable by partially taking an item.

Time Complexity: O(n log n) dominated by sorting; greedy iteration is O(n). Space O(n) for storing items.