systck
BAN USERLike someone mentioned below, its a coin change problem.
Code:
#include <iostream>
using namespace std;
int mcNuggets(int keys[], int key_size, int n)
{
if(key_size == 0)
return 0;
if(n == 0)
return 1;
int store[n+1];
for(int i = 1; i< n+1; i++)
store[i] = 0;
store[0] = 1;
for(int i = 0; i<key_size; i++)
for(int j = 0 ; j < n+1; j++) {
if(j >= keys[i])
store[j] = store[j] | store[j-keys[i]];
}
if(store[n] == 1)
return 1;
return 0;
}
int main(int argc, char **argv)
{
int keys[] = { 6, 9, 20};
int n;
cin >> n;
if(mcNuggets(keys, 3, n))
cout << "Possible" <<endl;
else
cout << "Not Possible" << endl;
}
Yes. Coin change. We don't care if its minimum or not. If we can make change for a given number, we're good. I've posted my solution as a comment.
- systck November 04, 2012