1 #include"header_file.h"
 2 using namespace std;
 3 
 4 int coin_num(vector<int> T,int i,int j)
 5 {
 6     if(i==1)
 7     {
 8         if(j%T[0]==0)
 9         {
10             return j/T[0];
11         }
12         else
13         {
14             return 9999;
15         }
16     }
17     else
18     {
19         int min;
20         min=coin_num(T,i-1,j);
21         int temp;
22         temp=j/T[i-1];
23         for(int m=0;m<=temp;m++)
24         {
25             if(min>(m+coin_num(T,i-1,j-m*T[i-1])))
26                 min=m+coin_num(T,i-1,j-m*T[i-1]);
27             
28         }
29         return min;
30     }
31 }
32 
33 vector<int> all_num(vector<int> T,int j)
34 {
35     vector<int> v;
36     for(int i=0;i<T.size();i++)
37         v.push_back(coin_num(T,i+1,j));
38 //    for(int i=0;i<T.size();i++)    //use for test
39 //        cout<<v[i]<<" ";
40         //v.push_back(coin_num(T,i+1,j));
41     return v;
42 }
43 
44 int find_min(vector<int> v)
45 {
46     int min=0;
47     for(int i=1;i<v.size();i++)
48     {
49         if(v[min]>v[i])
50             min=i;
51     }
52     return v[min];
53 }
54 
55 int main(void)
56 {
57     int n;
58     cout<<"input n:";
59     cin>>n;
60     
61     vector<int> T;
62     for(int i=0;i<n;i++)
63     {
64         int temp;
65         cin>>temp;
66         T.push_back(temp);
67     }
68     
69     int j;
70     cout<<"input j:";
71     cin>>j;
72     
73     vector<int> v;
74     v=all_num(T,j);
75     int min;
76     min=find_min(v);
77     cout<<"min:"<<min<<endl;
78 }