an algorithm that makes change for a given integer value V using the least number of coins Consider a collection of coins with denominations 1, 2, . . . , 2^k (2 to the power of k)
for some fixed k ≥ 0. Assuming that you have an unlimited supply of coins
of each value, describe an algorithm that makes change for a given
integer value V using the least number of coins. Explain why your
algorithm is correct.
 A: If $V=2W$ is even, then find the representation of $W$ and shift all coins to the next denomination.
If $V=2W+1$ is odd, then find the representation of $2W$ and above and add a $1$ cent coin.
Since you can recover the representation of $W$ from the representation of $V$, by induction this recursive algorithm gives the best possible representation.
This is the same as finding the representation of $V$ in base $2$, except that you're limited to a finite number of denominations and so cannot shift the largest denomination. For $V<2^{k+1}$, you can use at most one coin of each denomination. For $V\ge2^{k+1}$, you may need to repeat the largest coin: $$43=1+42=1+2[21]=1+2[1+2[10]]=1+2[1+2[8+2]]=1+2[1+2\cdot8+4]\\=1+2+4\cdot8+8=1+2+5\cdot8$$
So the algorithm can be simplified to: remove the largest multiple of $2^k$ from $V$ and express $V-n2^k$ in binary.
A: In C#:
// Use: PrintChange(270,8);
void PrintChange(int V, int k, int coinValue = 1){
  if(k==0) Console.WriteLine("Coins of value " + coinValue + " - " + V);
  if(V%2==1) Console.WriteLine("Coins of value " + coinValue + " - 1");
  return PrintChange(V/2, k-1, coinValue*2);
}

A: In C++
vector<int> changeBinary(int input)
{
    vector<int> result;
    int index = 0;
    while (input != 0) 
    {
        if (input & 1)
            //cout<<index<<endl;
            result.push_back(1); 
        else
            result.push_back(0);
        input >>= 1;// dividing by two
        index++;
    }
    return result;
}

void change(int v, int k)
{
    int temp = pow(2,k);
    if(v<=temp)
    {
        vector<int> v1;
        v1 = changeBinary(v);
        for(int i=0;i<v1.size();i++)
        {
            if(v1[i]) cout<<"Coins of type "<<pow(2,i)<<"- "<<v1[i]<<endl;
        }
    }
    else
    {
        int cnt = 0;
        while(v>=temp)
        {
            v = v-temp;
            cnt++;
        }
        cout<<"Coins of type "<<temp<<"- "<<cnt<<endl;
        vector<int> v1;
        v1 = changeBinary(v);
        int t2 = v1.size();
        for(int i=t2-1;i>=0;i--)
        {
            if(v1[i]) cout<<"Coins of type "<<pow(2,i)<<"- "<<v1[i]<<endl;
        }
    }
}

A: I wrote this following algorithm in Ruby, quite similar to the C# one submitted by @Abstraction. However, there are a few minor changes here.
If you take a look are the parameters, k is being created without having to supply it in the beginning. Also, as soon as k reaches 0, the program will `return' and stop. 
def print_change(v, k = Math.log(v, 2).to_i, coin_value = 1)

  if k == 0
    puts "#{v} coins of denomination: #{coin_value}"
    return
  end

  if v % 2 == 1
    puts "1 coins of denomination: #{coin_value}"
  end

  print_change(v/2, k-1, coin_value*2)
end

I hope this helps!
