#include
#include
#include //for INT_MAX
#include //for min
using namespace std;
vector coins; //The different types of coins
//Returns the smallest number of coins that are necessary to reach amount.
//If no possible, it returns -1
int numCoins(int amount)
{
if(amount == 0)
return 0;
else if(amount < 0)
return -1;
int minimum = INT_MAX; //A very big value
//Try out all coins
for(int coin : coins)
{
int num = numCoins(amount - coin); //Try out the coin: Let test recursively how many coins are necessary for the remaining amount.
if(num != -1) //If it is still possible to take this coin, look if it is better that what has already been tried out.
minimum = min(minimum, num);
}
if(minimum == INT_MAX) //If no single coins fitted, return -1
return -1;
else
return minimum + 1; //Otherwise take the smallest coin (+1) and the number of coins that are necessary for the remaining amount.
}
int main()
{
//number of types of coins
int n;
cin >> n;
coins = vector(n);
//read in the coin types
for(int i = 0; i < n; i++)
{
int coin;
cin >> coin;
coins[i] = coin;
}
//read in the amount
int amount;
cin >> amount;
//calculate the smallest number of coins that are necessary to reach the amount
cout << numCoins(amount) << endl;
}