Advertisement
Guest User

Untitled

a guest
Jul 17th, 2018
93
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.44 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3.  
  4.  
  5. using namespace std;
  6.  
  7.  
  8.  
  9. bool calcDP(bool dp[5001][1001], int targetvalue, int targetcoin, vector<int> coinvalues, int ncoins);
  10. int solve(bool dp[5001][1001], int tv,int tc);
  11. int main(){
  12. cout << "The Program has Intialized!" << endl;
  13. int coins;
  14. cin >> coins;
  15. vector<int> values;
  16. int tmp;
  17. for(int i = 0; i < coins;i++){
  18. cin >> tmp;
  19. values.push_back(tmp);
  20. }
  21.  
  22. bool dp[5001][1001];
  23. dp[0][0] = true;
  24. for(int coinnumber = 1; coinnumber < 1001;coinnumber++){
  25. for(int value = 0;value < 5001;value++){
  26. bool result = calcDP(dp,value,coinnumber, values, coins);
  27. dp[value][coinnumber] = result;
  28.  
  29. }
  30. }
  31. int queries,targetc,targetv;
  32. cin >> queries;
  33. for(int q = 0; q < queries;q++){
  34. cin >> targetc >> targetv;
  35. int solution = solve(dp,targetc,targetv);
  36. if(solution == -1){
  37. cout << "NO -1" << endl;
  38. }
  39. else{
  40. cout << "YES " << solution << endl;
  41. }
  42. }
  43. cout << "This Program Ran Successfully" << endl;
  44. return 0;
  45.  
  46. }
  47.  
  48. int solve(bool dp[5001][1001], int tv,int tc){
  49. for(int coins = tc;coins < 1001;coins++){
  50. if(dp[tv][coins]){return coins;}
  51. }
  52. return -1;
  53.  
  54. }
  55.  
  56. bool calcDP(bool dp[5001][1001], int targetvalue, int targetcoin, vector<int> coinvalues, int ncoins){
  57.  
  58. for(int idx = 0; idx < ncoins;idx++){
  59. if(targetvalue - coinvalues[idx] >= 0){
  60. if(dp[targetvalue-coinvalues[idx]][targetcoin-1]){
  61. return true;
  62. }
  63. }
  64. }
  65. return false;
  66. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement