Problem Statement
Explain the 0/1 Knapsack problem and its dynamic programming solution. What is the difference between 0/1 and fractional knapsack?
Explanation
The 0 or 1 Knapsack problem is a classic optimization problem where you have n items, each with a weight and value, and a knapsack with capacity W. The goal is to select items to maximize total value without exceeding the capacity. Each item can be either taken completely or not taken at all, hence the name 0 or 1.
The problem exhibits optimal substructure because the optimal solution for n items and capacity W either includes the nth item or excludes it. If we include the nth item, we need the optimal solution for n minus 1 items with capacity W minus weight of nth item. If we exclude it, we need the optimal solution for n minus 1 items with capacity W. We take the maximum of these two choices.
The DP solution uses a 2D table where dp of i of w represents the maximum value achievable using the first i items with capacity w. The recurrence relation is: if weight of item i is less than or equal to w, then dp of i of w equals max of value of i plus dp of i minus 1 of w minus weight of i, which is including the item, and dp of i minus 1 of w, which is excluding the item. Otherwise, dp of i of w equals dp of i minus 1 of w as we cannot include the item.
Base cases are dp of 0 of w equals 0 for all w, meaning with zero items we get zero value, and dp of i of 0 equals 0 for all i, meaning with zero capacity we get zero value. The evaluation order is row by row, processing items one by one, and within each row, processing capacities from 0 to W. The final answer is dp of n of W.
Time complexity is O of n times W where n is the number of items and W is knapsack capacity. We fill a table of size n plus 1 by W plus 1 with constant work per cell. Space complexity is O of n times W for the 2D table, though it can be optimized to O of W using a 1D array by processing items one at a time.
The space-optimized solution uses only one row by observing that we only need the previous row to compute the current row. We can use a single array and update it in-place by iterating from right to left to avoid overwriting values we still need.
The fractional knapsack problem differs in that you can take fractions of items, not just whole items. This changes the problem fundamentally. Fractional knapsack can be solved optimally using a greedy approach. Sort items by value-to-weight ratio in descending order. Take items in this order, taking as much as possible of each item until the knapsack is full. If an item does not fit completely, take the fraction that fits. Time complexity is O of n log n for sorting.
The key difference is that 0 or 1 knapsack requires dynamic programming with O of n times W time because you cannot make locally optimal choices. You must consider combinations of items. Fractional knapsack can use greedy with O of n log n time because taking items with highest value-to-weight ratio is always optimal when fractions are allowed.
Applications of 0 or 1 knapsack include resource allocation with constraints, portfolio optimization, cargo loading where items cannot be split, and project selection with budget constraints. The problem is NP-complete in general, but the DP solution is pseudo-polynomial with time depending on W.