Problem Statement
For which problem does a greedy approach NOT guarantee an optimal solution?
Explanation
The 0 or 1 Knapsack problem requires dynamic programming because greedy approaches like selecting items by highest value or highest value-to-weight ratio do not guarantee optimal solutions. You cannot take fractional items, so local optimal choices may lead to suboptimal global solutions.
Activity selection, Huffman coding, and Dijkstra's algorithm all exhibit the greedy choice property where local optimal choices lead to global optimum. In contrast, knapsack requires considering all combinations of items, making it a classic DP problem. The fractional knapsack where you can take parts of items can be solved greedily, but 0 or 1 knapsack cannot.
Code Solution
SolutionRead Only
// 0/1 Knapsack - Greedy FAILS
// Items: [(value=60, weight=10), (100, 20), (120, 30)]
// Capacity: 50
// Greedy by value/weight ratio:
// Ratios: [6, 5, 4]
// Pick: (60,10) + (100,20) = value 160, weight 30
// Remaining capacity: 20, can't fit (120,30)
// Total: 160
// Optimal DP solution:
// Pick: (100,20) + (120,30) = value 220, weight 50
// Total: 220 > 160
// DP approach needed:
int knapsack(int[] val, int[] wt, int W) {
int[][] dp = new int[n+1][W+1];
for (int i = 1; i <= n; i++) {
for (int w = 1; w <= W; w++) {
if (wt[i-1] <= w)
dp[i][w] = max(val[i-1] + dp[i-1][w-wt[i-1]],
dp[i-1][w]);
else
dp[i][w] = dp[i-1][w];
}
}
return dp[n][W];
}