title: Denominate the amount with the minimum number of coins with a given face value. Greedy problem
body: <p>I have the C++ function to do. It works fine, but there are some cases where it works bad - "greedy problem".</p>
  
  <p>My C++ code:</p>
  
  <pre><code>#include &lt;vector&gt;
  #include &lt;algorithm&gt;
  
  std::vector&lt;int&gt; ans;
  
  std::vector&lt;int&gt; get_change(const std::vector&lt;int&gt; &amp;denominations, int amount) {
      //pure algo
      std::vector&lt;int&gt; money = denominations;
      std::vector&lt;int&gt; count;
      ans.clear();
      count.assign(money.size(), 0);
      std::sort(money.begin(), money.end());
      int summ = amount;
      for (int i = count.size()-1; i &gt;= 0; i--) {
          count[i] = summ / money[i];
          summ = summ % money[i];
          if (summ==0)
              break;
      }
  
  
      //ans generation
      for (int i = 0; i &lt; money.size(); i++)
          for (int j = 0; j &lt; count[i]; j++)
              ans.push_back(money[i]);
      return ans;
  }
  </code></pre>
  
  <p>Greedy problem sample: <code>get_change({ 1, 6, 9 }, 30)</code> will return <code>{ 1, 1, 1, 9, 9, 9 }</code>, but not <code>{ 6, 6, 9, 9 }</code>.</p>
  
  <p>The task is to improve this algorithm to get the same answer.</p>