display | more...
This is a problem that comes up in many Algorithms 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

Log in or register to write something here or to contact authors.