[description of the problem]
There are many ways to make a sum of money with a few coins. For example, 6 coins have a face value of 2, 5, 10, 20, 50, 100. It is used to collect 15 yuan, and can use 5 2 yuan, 1 5, or 3 5 yuan, etc. Obviously, it takes at least 2 coins to make up 15 yuan. Your task is to calculate the minimum amount of money needed to make up a given amount of money by giving a number of different coin denominations.
[input] there can be more than one test case. The first line of each test case is the amount of money to be made up M (1 < = M < = 2000, integer), and in the next row, the first integer K (1 < = K < = 10) represents the number of currencies, followed by K, which is different from each other, Ki (1 < = Ki < = 1000). The end of the input M=0.
[output] each test case outputs one line, that is, the sum of money value M the minimum number of coins. If the money fails, output "Impossible". You can assume that there is an unlimited amount of money to be collected.
[input case] 1562510205010011 20
[output example] 2 Impossible
solved:
#include <stdio.h>
int v[6] = {2,5,10,20,50,100};
int min(int a,int b) { return a<b?a:b; }
int solve(int t,int i=0)
{if(t==0) return 0;
if(i>=6 || t<v[i]) return false;
return min(solve(t,i+1),solve(t-v[i],i)+1);}
int main()
{int z;
printf("请输入数值");
scanf("%d",&z);
int n = solve(z);
printf("%d\n",n);
return 0;}