Within the weight limit, what is the most valuable combination?
The knapsack has a fixed weight limit. Choose from the items below so that their total weight stays within the limit while their total value is as large as possible. When you are done, click "Show Optimal Combination" to compare your choice with the computer's answer.
Why is this a difficult problem? If there are n items, there are 2ⁿ possible combinations. Even with just 30 items, that is more than 1 billion combinations, making it impractical to check them all. Computers solve this problem much faster using a clever method called dynamic programming (DP).
Knapsack weight limit15kg
Weight 0/15kgValue 0
💡 The knapsack problem is a famous optimization problem that represents a whole class of tasks like loading packages onto a delivery truck or choosing investments within a budget: "get the maximum benefit from limited resources."