Knapsack Problem, Cryptography, and the Presidential Election

Abstract

The 0-1 Knapsack Problem is an NP-hard optimization problem that has been studied extensively since the 1950s, due to its real world significance. The basic problem is that a knapsack with a weight capacity c is to be filled with a subset of n items. Each item i, has a weight value wi and a profit value pi. The goal is to maximize total profit value without the having the total weight exceed the capacity. In this thesis, the 0-1 Knapsack Problem is introduced and some of the research and applications of the problem are given. Pisinger's branch-and-bound algorithm that will converge to an optimal solution is presented. One of the earliest applications of the knapsack problem, the knapsack cryptosystems, is then discussed. The earliest knapsack cryptosystem, the Merkle-Hellman Cryptosystem, is described along with how Adi Shamir broke this cryptosystem. Generating functions are then used to provide a number of solutions to a knapsack problem. Using the generating function of the knapsack problem, the paper concludes with an application on the Electoral College.