Integer Linear Programming for the 0/1 Knapsack Problem: Exact Optimization Using Julia/JuMP and a Critical Comparison with Greedy Algorithms

The 0/1 knapsack problem is a canonical NP-hard problem in combinatorial optimization with widespread applications in resource allocation, scheduling, cryptography, and decision-making systems. Despite its apparent simplicity, the problem exhibits significant computational complexity when exact solutions are required. Greedy heuristics are frequently employed due to their computational efficiency, but they do not guarantee global optimality. In this paper, we present a rigorous Integer Linear Programming (ILP) formulation of the 0/1 knapsack problem and demonstrate its exact solution using the Julia programming language and the JuMP optimization framework. A concrete numerical example is analyzed and solved using both open-source and commercial solvers. The integration of the high-performance Gurobi solver is discussed in detail. Furthermore, a comprehensive theoretical and practical comparison between ILP and greedy algorithms is provided, highlighting fundamental differences in decision-making scope, optimality guarantees, and computational trade-offs.