Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- using namespace std;
- bool calcDP(bool dp[5001][1001], int targetvalue, int targetcoin, vector<int> coinvalues, int ncoins);
- int solve(bool dp[5001][1001], int tv,int tc);
- int main(){
- cout << "The Program has Intialized!" << endl;
- int coins;
- cin >> coins;
- vector<int> values;
- int tmp;
- for(int i = 0; i < coins;i++){
- cin >> tmp;
- values.push_back(tmp);
- }
- bool dp[5001][1001];
- dp[0][0] = true;
- for(int coinnumber = 1; coinnumber < 1001;coinnumber++){
- for(int value = 0;value < 5001;value++){
- bool result = calcDP(dp,value,coinnumber, values, coins);
- dp[value][coinnumber] = result;
- }
- }
- int queries,targetc,targetv;
- cin >> queries;
- for(int q = 0; q < queries;q++){
- cin >> targetc >> targetv;
- int solution = solve(dp,targetc,targetv);
- if(solution == -1){
- cout << "NO -1" << endl;
- }
- else{
- cout << "YES " << solution << endl;
- }
- }
- cout << "This Program Ran Successfully" << endl;
- return 0;
- }
- int solve(bool dp[5001][1001], int tv,int tc){
- for(int coins = tc;coins < 1001;coins++){
- if(dp[tv][coins]){return coins;}
- }
- return -1;
- }
- bool calcDP(bool dp[5001][1001], int targetvalue, int targetcoin, vector<int> coinvalues, int ncoins){
- for(int idx = 0; idx < ncoins;idx++){
- if(targetvalue - coinvalues[idx] >= 0){
- if(dp[targetvalue-coinvalues[idx]][targetcoin-1]){
- return true;
- }
- }
- }
- return false;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement