title: Unbounded knapsack/coin change with optimal solution for non-standard coins
body: <p>I have the following problem:</p>
  
  <blockquote>
    <p>Given a target size N and some denominations of some randomly
    generated coins stored in array denominations[] check using dynamic
    programming if there is an optimal solution which will fill the entire
    target with the least amount of coins used.</p>
  </blockquote>
  
  <p>This is a typical example of coin change problem, however unlike real life currency where each denomination is carefully picked so that any target can be matched this is not the case. </p>
  
  <p>I am familiar with the algorithm used in coin change problem and how to construct a dynamic programming array to find the solution but how do I check if there is a solution in the first place? </p>