Ask Question
22 April, 06:03

Given an unlimited supply of coins of denomination x1, x2, ..., xn, we wish to make change for a value v. Weare seeking an O (nv) dynamic-programming for the following problemInput: x1, ..., xn; vQuestion: Is it possible to make change for v using coins of denominations x1, ..., xn

Answers (1)
  1. 22 April, 06:20

    C (t) = min

    x∈{x1, ..., xn}

    C (t - x) + 1

    Step-by - step Solution

    Subtasks. For any 1 ≤ t ≤ v, let C (t) = c where c is the minimum number of coins required to create the

    total t, using the given denominations. If it is not possible for any number of coins, then C (t) = ∞.

    Recurrence Relation. We calculate C (t) based on C (s) for 1 ≤ s < t. The recurrence relation is:

    C (t) = min

    x∈{x1, ..., xn}

    C (t - x) + 1

    Base Case, Final Solution, Evaluation Order. We initialize C (0) = 0. We also declare that C (u) = ∞

    when u < 0. The final solution is just whether C (v) is less than or equal to k. The evaluation order is to

    start at t = 1, compute C (t), increment t and repeat.

    Correctness. We will show by induction that the subtask C (t) is correctly computed for all t. The base

    case C (0) = 0 is true: by using 0 coins, we have a total of 0, and 0 coins is the least we could possibly use.

    For the inductive case, observe that for any x ∈ {x1, ..., xn}, given a way to produce a total t-x with c coins,

    we may produce a total t using c + 1 coins, so we know C (t) ≤ 1 + C (t - x). As we wish to minimize the

    total coins used, we care only about the minimal way to construct the value t-x and our use of the previous

    subtask is correct. We take the minimum over all n possibilities. This is exhaustive: every combination of

    c + 1 coins totalling t can be decomposed into a combination of c coins and an extra final coin. We remark

    that C (t - x) = ∞ means C (t - x) + 1 is also ∞, and that the minimum in the recurrence relation will

    be infinite if and only if all C (t - x) are infinite, which implies there is no valid way to create the total t.

    Thus C (t) is correctly computed. Our evaluation order is also correct, as computing C (t) requires only the

    precomputed values C (s) for s < t.
Know the Answer?