Problem idea
A thief has a knapsack of limited capacity W. Each item has value v and weight w. Unlike 0/1 knapsack, the thief may take fractions of items.
Greedy rule
Sort items by value density (v / w) in descending order.
Take items fully while they fit; otherwise take the fraction that fits.
Why greedy works here
- Fractions smooth the solution space.
- Taking the best density first can never reduce the optimal value.
- Greedy-choice property and optimal substructure both hold.
Contrast
In 0/1 knapsack, fractions are not allowed. Early greedy choices can block better combinations, so dynamic programming is required.
Click Start to begin filling the bag using the greedy rule.
| Item | Value | Weight | v/w | Decision |
|---|---|---|---|---|
| A | 60 | 10 | 6.0 | — |
| B | 100 | 20 | 5.0 | — |
| C | 120 | 30 | 4.0 | — |
Advanced (Optional): Try your own data Up to 6 items
Change capacity and items, then click Run Greedy to see decisions (full / fraction) for each item. Items are sorted by value/weight automatically.
⚠️ Some inputs may not require a fraction. Greedy still works, but the ✂️ step may not appear.
| Item | Value | Weight | v/w | Decision |
|---|