Recall that the general change problem is: Given the k coins values and a value v, find a way to give the value v in change using as few coins as possible (sufficient coins of each denomination are available). The following greedy algorithm: remaining := v; for i = k-1 downto 0 do take (remaining div c_i) coins of denomination c_i remaining := remaining (remaining div c_i)*c_i

can fail with the coin values are arbitrary, and it always gives optimal solution when there is some positive integer b such that each . Prove or disprove the following: If for each , then the above greedy algorithm will produce an optimal solution.

Co