How do dynamic programming and greedy algorithms differ, and in which problem can greedy fail?

• A. Dynamic programming solves subproblems exhaustively; greedy makes locally optimal choices; greedy can fail in 0/1 knapsack where choosing the largest value-to-weight ratio doesn't yield the optimal solution.
• B. Dynamic programming is always faster than greedy for every problem.
• C. Greedy always yields the optimal solution for 0/1 knapsack.
• D. Dynamic programming uses randomness to explore possible solutions.

Answer: (A)

Dynamic programming and greedy algorithms differ in how they build solutions. Dynamic programming tackles a problem by breaking it into subproblems, solving each subproblem, and storing those results so they can be reused. This lets it consider many possible combinations and guarantees an optimal overall solution when the problem has overlapping subproblems and optimal substructure. Greedy approaches, on the other hand, pick the best local option at each step and never revisit those decisions, hoping the local choices add up to a global optimum. That can work for some problems but not for all.

A classic example where greedy can fail is the 0/1 knapsack problem. If you choose items based on the highest value-to-weight ratio, you might fill the capacity with items that seem best individually but prevent picking a different combination of smaller items that would yield a larger total value. Dynamic programming avoids this pitfall by evaluating all feasible combinations up to the capacity, ensuring the best total value is found.

Note that in fractional knapsack, greedy is optimal because you can take fractions of items, aligning local choices with the global optimum. Here, the issue arises specifically in the 0/1 version, where you must either take an item or leave it.