How do I solve the coin problem?

How do I solve a change making problem taking at most one coin of one type using dynamic programming?

• Given a list of N coins, their values (V1, V2, ... , VN), and the total sum S. Find the minimum number of coins the sum of which is S (you can use at most one coin of one type), or report that it's not possible to select coins in such a way that they sum up to S.

• Answer:

  what is the constraint one the value of n ?? is it less than 20 ?   if n around 20 then we can use (bitmasking+dp) along with memoisation to solve the problem with dp[i][j] where i is the sum required to get down to zero and j is the bitmask which all bits are set are more to be used and the bits which are not set are already used so dp[n][2^n] will do the job . For the constraint n = 1000 around   we will use two array , first array a boolean (used)one size = cumulative sum of all the elements of n summation vi where 1<=i<=n . and set used[0] = true ,that means sum of zero is possible and dp[0] = 0,which means 0 coins are required to get sum as 0, Then for every element 1<=i<=n , we check whether from the coin number with denomination vi we can get a particular sum .... so the code is as follows; int dp[cumulative_sum]; bool used[cumulative_sum]; memset(dp,INT_MAX,sizeof dp); memset(used,false,sizeof used); dp[0] = 0; used[0] = false; for(int i=0;i<n;i++){   for(int j=S;j>=0;j--){      if(used[j]){          used[j+v[i]] = true;          dp[j+v[i]] = min(dp[j+v[i]],dp[j]+1);      }   } } if(dp[S] != INT_MAX)  cout << dp[S]  << endl; else  cout << "not possible" < endl; Hope you get the logic behind it :)