Advertisement
Guest User

help

a guest
Oct 22nd, 2019
123
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.86 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // m is size of coins array (number of different coins)
  5. int minCoins(int coins[], int m, int V)
  6. {
  7. // base case
  8. if (V == 0) return 0;
  9.  
  10. // Initialize result
  11. int res = INT_MAX;
  12.  
  13. // Try every coin that has smaller value than V
  14. for (int i=0; i<m; i++)
  15. {
  16. if (coins[i] <= V)
  17. {
  18. int sub_res = minCoins(coins, m, V-coins[i]);
  19.  
  20. // Check for INT_MAX to avoid overflow and see if
  21. // result can minimized
  22. if (sub_res != INT_MAX && sub_res + 1 < res)
  23. res = sub_res + 1;
  24. }
  25. }
  26. return res;
  27. }
  28.  
  29. // Driver program to test above function
  30. int main()
  31. {
  32. int m,V,i,coins[500];
  33. cin>>m>>V;
  34.  
  35. for(i=0;i<m;i++)
  36. {
  37. cin>>coins[i];
  38. }
  39. cout << "Minimum coins required is "
  40. << minCoins(coins, m, V);
  41. return 0;
  42. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement