The Knapsack Problem is a classic combinatorial optimization problem: given n items with weights wᵢ and values vᵢ, and a knapsack with capacity W, select items to maximize total value without exceeding capacity. Formally: maximize Σvᵢxᵢ subject to Σwᵢxᵢ ≤ W, where xᵢ ∈ {0,1}. Variants include: 0/1 knapsack (items cannot be divided), fractional knapsack (items can be divided), multiple knapsack, and multidimensional knapsack. Solution methods include dynamic programming, branch and bound, and greedy algorithms (for fractional version).