This is a problem that comes up in many Algorithm
s classes, because it is a good problem to illustrate the use of dynamic programming
. There are many different formulations of the knapsack
problem, but all of them feature putting different sized
items into a knapsack of fixed size.
This particular formulation comes from Manber1:
"Given an integer K and n items of different sizes such that the ith item has an integer size ki, find a subset of the items whose sizes sum exactly to K, or determine that no such subset exists."
Variations include finding the biggest subset that would fit in K, or finding the subset with the most number of items, etc. Variations of the knapsack problem are used to solve packing large warehouses. Knapsack problems are very closely related to "bin packing" problems.
I should also note that the knapsack problem is NP-Complete
1 Udi Manber
, "Introduction to Algorithms a Creative Approach", p. 108