嗯哼，別人問的問題，看的我也頭暈，百度了一下動態規劃，看了看才想起來該怎麼做，今天寫了寫代碼，實現了~
要求是遞歸，動態規劃，想了想這種方法也是最簡單的~
所謂動態規劃：把多階段過程轉化為一系列單階段問題，利用各階段之間的關系，逐個求解。動態規劃算法通常用於求解具有某種最優性質的問題。在這類問題中，可能會有許多可行解。每一個解都對應於一個值，我們希望找到具有最優值的解。動態規劃算法與分治法類似，其基本思想也是將待求解問題分解成若干個子問題，先求解子問題，然後從這些子問題的解得到原問題的解。與分治法不同的是，適合於用動態規劃求解的問題，經分解得到子問題往往不是互相獨立的。若用分治法來解這類問題，則分解得到的子問題數目太多，有些子問題被重復計算了很多次。如果我們能夠保存已解決的子問題的答案，而在需要時再找出已求得的答案，這樣就可以避免大量的重復計算，節省時間。我們可以用一個表來記錄所有已解的子問題的答案。不管該子問題以後是否被用到，只要它被計算過，就將其結果填入表中。這就是動態規劃法的基本思路。（摘自百科）（時間復雜度為一個多項式的復雜度）
背包問題(Knapsack problem)是一種組合優化的NP完全問題。問題可以描述為：給定一組物品，每種物品都有自己的重量和價格，在限定的總重量內，我們如何選擇，才能使得物品的總價格最高。問題的名稱來源於如何選擇最合適的物品放置於給定背包中。
題目如截圖：
解題思路：
n代表面值
n為1，直接看是否可以整除；
n>1，看在沒有第n個面值的時候多少，然後看有1個、2個....j/n個面值為n的時候需要幾枚硬幣，取最小值
將這些直接存在數組中，然後去數組裡的最小值
代碼：
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 }
