📢 Too many exams? Don’t know which one suits you best? Book Your Free Expert 👉 call Now!

    Question

    A greedy algorithm is used to make change for a given

    amount using a set of coin denominations. For denominations {1, 5, 10, 25} and an amount of 30, it works correctly. However, for denominations {1, 4, 6} and an amount of 8, it fails to find the optimal solution (e.g., 4+4 vs 6+1+1). What is the fundamental reason for this failure, which is a common debugging point for greedy algorithms?
    A The algorithm does not sort the coin denominations. Correct Answer Incorrect Answer
    B The problem does not satisfy the greedy choice property. Correct Answer Incorrect Answer
    C The base case for the recursion is incorrect. Correct Answer Incorrect Answer
    D The algorithm uses a stack instead of a queue. Correct Answer Incorrect Answer
    E The input amount is too small for the greedy approach. Correct Answer Incorrect Answer

    Solution

    The correct answer is B

    Practice Next
    More IT Operating System Questions
    ask-question