Knapsack
← Back to Classic Problems (DP)
Given items with weights and values, determine the most valuable combination that fits within a weight limit. The 0/1 knapsack (items cannot be divided) is solved with DP in O(nW) pseudo-polynomial time. A canonical NP-hard optimization problem.