Integer Knapsacks and the Frobenius Problem

Document Type



Mathematics (CMC)

Publication Date



Given unlimited supply of N > 1 types of objects of respective integer weights a_1,...,a_N and corresponding integer prices p_1,...,p_N, the integer knapsack problem aims to maximize the value of a knapsack that can hold at most the weight W. This is an important problem in operations research, which often arises in resource allocation with financial constraints; it is known to be NP-complete. The integer knapsack problem is closely related to another famous NP-hard problem, the linear Diophantine Frobenius problem (FP): assuming that the weights a_1,...,a_N are relatively prime, find the largest weight that such a knapsack CANNOT have. I will discuss this connection, and will then talk about FP in more details, reviewing some of the recent results on this extensively studied problem.


This lecture was given during the Statistics/Operations Research/Math Finance seminar at the Claremont Colleges in April 2011.

Rights Information

© 2011 Lenny Fukshansky

Terms of Use & License Information

Terms of Use for work posted in Scholarship@Claremont.