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 a set of items with weights and values, and a knapsack of limited capacity, select items (allowing fractional amounts) to maximize total value without exceeding the weight capacity. Use the visualizer to step through the greedy algorithm, observing how items are selected by value-to-weight ratio.

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

knapsack.svg — Fractional Knapsack Visualization

Selected (Full)

Partial

Available

Capacity: 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

Aspect	Complexity
Time	O(n log n)
Space	O(n)
Greedy Choice	Max Ratio

Implementation

Language:

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.

fractional_knapsack.py

1def fractional_knapsack(items, capacity):
2"""Solve fractional knapsack with greedy algorithm"""
3# Sort by value/weight ratio descending
4items.sort(key=lambda x: x[1] / x[0], reverse=True)
5total_value = 0.0
6used_capacity = 0.0
7
8for weight, value in items:
9if used_capacity + weight <= capacity:
10# Take item fully
11total_value += value
12used_capacity += weight
13else:
14# Take fractional part
15remaining = capacity - used_capacity
16fraction = remaining / weight
17total_value += value * fraction
18break
19return total_value
20
21# Example usage
22items = [(10, 60), (20, 100), (30, 120)]
23result = fractional_knapsack(items, 50)
24print("Maximum value:", result)

Explanation

Docstring: Function docstring describes purpose: solve fractional knapsack with greedy algorithm to maximize value.

sort() with lambda: Line 4 sorts items using lambda key=lambda x: x[1]/x[0] (value/weight) in reverse order. Single-line replacement for C's qsort with comparator.

Initialization: total_value and used_capacity track algorithm state; starting both at 0.0 allows float precision for fractional parts.

Greedy Loop: Iteration checks if item fits fully in remaining capacity (line 9). If yes, add all; if no (line 13), compute remaining space and fraction to maximize partial value.

Fraction Calculation: Line 15-16 computes remaining capacity, then fraction as decimal ratio of item weight. Line 17 multiplies fractional amount by item value.

Time Complexity: O(n log n) for sorting; greedy selection loop runs at most n times = O(n). Python's built-in sort uses Timsort, highly optimized for real-world data.