Integer Knapsacks and the Frobenius Problem

Given unlimited supply of N \u3e 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