AlgorandSIMULATION v1.0
Sequential Engines(17)
Parallel Engines
Greedy Algorithm (Fractional Knapsack)
sequentialRAMAn optimization algorithm that makes locally optimal choices at each step to find a global optimum. Demonstrates the Fractional Knapsack problem where items are sorted by value-to-weight density ratio and greedily selected to maximize total value.
SIMULATION STEP PROGRESSStep 1 / 1
SPEED (50%)
SIZE (6)
💡 Tip: Enter integers between 1 and 99. Max size is 10.
Code Workspace
1procedure FractionalKnapsack(Items, Capacity)
2 compute density v[i] / w[i] for each item
3 sort Items by density descending
4 totalValue := 0, currentWeight := 0
5 for each item in sorted Items do
6 if currentWeight + item.weight <= Capacity then
7 currentWeight += item.weight
8 totalValue += item.value
9 take 100% of item
10 else
11 remaining := Capacity - currentWeight
12 totalValue += item.value * (remaining / item.weight)
13 take fraction (remaining / item.weight) of item
14 break
15 end if
16 end for
17end procedure
Currently highlights executing branch
RUNTIME COST METRICS
Comparisons0
Memory Writes0
Memory Reads0
Elements Swapped0
Computational Model:RAM (Single Core)
Theoretical Bound:O(N log N)
Space Complexity:O(N)
Communication Cost:0 (Shared Bus)
THEORETICAL ANALYSIS & RESEARCH
Conceptual Focus: An optimization algorithm that makes locally optimal choices at each step to find a global optimum. Demonstrates the Fractional Knapsack problem where items are sorted by value-to-weight density ratio and greedily selected to maximize total value.
Real-world Industrial Applications:
- Resource allocation and bandwidth throttling
- Financial portfolio asset allocation
- Data compression (Huffman coding trees)
- Job and activity scheduling