Online Tool Store
· 4 min read
How to Pick the Best Items Within a Limit
Heshan Fernando
Co-founder & COO
Fourteen things you could take, a twelve kilogram limit, and each item worth a different amount to you. Or nine projects, one budget, and different expected returns. Or a set of features, one release, and limited engineering time.
They’re the same problem, it has a name, and the obvious approach to solving it gives the wrong answer.
Why greedy selection fails
The instinctive method: calculate value per kilogram for each item, sort descending, and take from the top until you run out of capacity.
It’s fast, it’s intuitive, and it’s not optimal — because items are indivisible.
Consider a 12 kg limit and three items: A weighing 7 kg worth 70 (10 per kg), B weighing 6 kg worth 54 (9 per kg), C weighing 6 kg worth 54 (9 per kg).
Greedy takes A first at the best ratio, leaving 5 kg — not enough for B or C. Total value: 70.
The optimal answer is B and C: 12 kg exactly, total value 108.
Greedy failed because taking the best ratio left a gap nothing fits. The optimal solution needs to consider how items combine, not just how good each is individually.
This matters whenever the limit is a hard constraint and the items are all-or-nothing.
| Approach | Result | Optimal? |
|---|---|---|
| Greedy by value/weight | 70 | No |
| Optimal (B + C) | 108 | Yes |
When greedy is optimal
One case: the fractional knapsack, where items can be divided. Take as much of the best ratio as fits, then move down. Since you can always fill the remaining capacity with a fraction of the next item, no gaps occur and greedy is provably optimal.
That’s why the distinction matters. Splitting a budget across projects where partial funding is meaningful is fractional and greedy works. Choosing which whole items to pack isn’t, and it doesn’t.
How it’s actually solved
Dynamic programming. Build a table of the best achievable value for every capacity from zero up to your limit, considering each item in turn. Each cell asks: is it better to include this item or not, given the capacity available?
It’s efficient when capacities are integers of moderate size, which covers most practical uses. The problem is NP-hard in general, so very large instances with large capacity values become impractical — but a packing list or a project portfolio is comfortably solvable.
Where it turns up
Packing. The original framing, and the least commercially important.
Budget allocation. Choosing which projects to fund within a fixed budget, where projects are all-or-nothing.
Cargo and container loading. Weight or volume limited, discrete items.
Cutting stock. Fitting pieces into standard material lengths.
Release planning. Features within a fixed engineering capacity.
The common shape: discrete items, one hard limit, and a value you’re maximising.
Common mistakes to avoid
- Using greedy selection and assuming it’s optimal.
- Applying it where the constraint is soft, in which case the answer is a judgement rather than an optimisation.
- Assigning values that are really guesses and then treating the output as precise.
- Ignoring dependencies between items — if project B requires project A, this model doesn’t capture that.
- Optimising a portfolio where the real constraint is people rather than money.
How to do it with Knapsack Solver
The Knapsack Solver finds the exact optimum and compares it against greedy.
- List each item with its weight or cost and the value you assign it.
- Set the capacity — a weight limit, a budget, a time box.
- Read the optimal set and compare it against what greedy would have chosen.
- Sanity check the values, since the output is only as good as they are.
Other optimisation tools are in the tools directory.
Frequently asked questions
Why isn’t picking the best value-per-weight optimal?
Because items are indivisible. A slightly worse ratio item may fill the remaining space perfectly where the better one doesn’t fit at all. Greedy is optimal only when items can be split.
What is this actually used for?
Packing decisions, budget allocation across projects, cargo loading, and cutting stock problems. Anything choosing a subset under a single hard limit has this shape.
Is the problem hard?
It’s NP-hard in general, but dynamic programming solves it efficiently when capacities are integers of moderate size, which covers most practical uses.
Final thought
Compare the optimal set against your instinct. The difference is usually one item you’d have taken and shouldn’t have — and seeing that once changes how you approach the next allocation.