[Verse 1]
Got a knapsack problem but the rules have changed
Items can be split up, game's been rearranged
Unlike zero-one where it's all or none
Fractional lets you take just a portion of one
Start by calculating value per unit weight
Sort them high to low, don't hesitate
Greedy algorithm's the way to go
Take the highest ratio, let that value flow
[Chorus]
Sort by ratio, value over weight
Take the best first, don't you hesitate
Fill it up until the bag is tight
Fractional knapsack, greedy gets it right
Value divided by the weight you see
Highest ratio first, that's the key
When the space runs out, take a fraction clean
Optimal solution, best you've ever seen
[Verse 2]
Linear time to sort if ratios are known
Otherwise n log n when they're not shown
Start with empty knapsack, zero weight inside
Pick the item with the highest value ride
If the whole item fits within the space
Add it completely, pick up the pace
But when you hit the limit of your bag
Take a fraction, don't let efficiency drag
[Chorus]
Sort by ratio, value over weight
Take the best first, don't you hesitate
Fill it up until the bag is tight
Fractional knapsack, greedy gets it right
Value divided by the weight you see
Highest ratio first, that's the key
When the space runs out, take a fraction clean
Optimal solution, best you've ever seen
[Bridge]
Continuous relaxation of the discrete case
Greedy choice property shows its face
Unlike zero-one, no dynamic needed
Simple greedy strategy, optimality conceded
Calculate remaining capacity in the sack
Multiply by ratio, add value back
Linear programming dual, shadow price clear
Marginal value of capacity crystal here
[Verse 3]
Implementation's clean, just sort and scan
Keep a running total of your current plan
When current weight plus next item's too much
Take the fraction that fits, maintain the touch
Remaining space divided by item weight
Times the item's value, calculate
Add it to your total, you're all done
Fractional knapsack mastered, victory won
[Chorus]
Sort by ratio, value over weight
Take the best first, don't you hesitate
Fill it up until the bag is tight
Fractional knapsack, greedy gets it right
Value divided by the weight you see
Highest ratio first, that's the key
When the space runs out, take a fraction clean
Optimal solution, best you've ever seen
[Outro]
Greedy's got the answer when fractions are allowed
Optimal every time, say it loud and proud
Sort by ratio, that's your golden rule
Fractional knapsack, now you got the tool