在過去24小時裡，一直被這題折騰著。。。
題目：
A Math game
Time Limit: 2000/1000MS (Java/Others) Memory Limit: 256000/128000KB (Java/Others)
Problem Description
Recently, Losanto find an interesting Math game. The rule is simple: Tell you a number H, and you can choose some numbers from a set {a[1],a[2],......,a[n]}.If the sum of the number you choose is H, then you win. Losanto just want to know whether he can win the game.
Input
There are several cases.
In each case, there are two numbers in the first line n (the size of the set) and H. The second line has n numbers {a[1],a[2],......,a[n]}.0<n<=40, 0<=H<10^9, 0<=a[i]<10^9,All the numbers are integers.
Output
If Losanto could win the game, output "Yes" in a line. Else output "No" in a line.
Sample Input
10 87
2 3 4 5 7 9 10 11 12 13
10 38
2 3 4 5 7 9 10 11 12 13
Sample Output
No
Yes
簡述之就是子集和問題。
AC 之後，發現原來寫代碼的過程如此有趣。。。。
solution 1 直接DFS 運行時間 200.8s
針對數組中的每個元素，要麼選中，要麼不選。 結果是 Time Limit Exceeded （指超過題目要求的 1000MS)
遍歷過程類似於二叉樹，復雜度是指數級， 2^n
Solution 2 加點剪枝處理 運行時間 166.7 s
在sulotion 1 的基礎上，做個判斷，一旦累加的記過超過 H，則不進行後面的累加。
結果仍然 Time Limit Exceeded。 感覺沒有根本性的變化！
（如果超過H的話，就不往下走了，相比第一個方案，效率有了一丟丟提升, 筆記本風扇依然狂轉）
Solution 3 對輸入進行預處理 運行時間 4.1 s
因為輸入的數據是比較小的，所以進行排序的時間消耗非常小，但是效率的提升非常明顯！
前兩個方案，我等了很久，都沒有出現結果。 但是排序之後，等幾秒鐘就看到結果了。哇，那個激動啊。。。
我畫了個圖，發現一旦數據是排序的，那麼剪枝的效果將會非常明顯，所以這導致了效率的大幅提升
雖然有所提升，但是提交之後，依然 Time Limit Exceeded （此後經過1個多小時的修改測試，還是超時） 深夜了，休息。。。
新的一天, 起床，繼續 coding~~~
Solution 4 對遍歷方向進行處理 運行時間 3.4 s
可能是思維慣性，老想著從無到有進行遍歷，所以總是往不選的方向遍歷，導致浪費很多無用的時間。
所有修改搜索順序，往選中的方向進行遍歷。
結果超時！ 仔細思考之後，發現剪枝的效果不明顯，原因在於我是按升序排序的，應該改為 降序排序
Solution 5 AC！ 運行時間 0.4s
進行降序排序，明顯提高剪枝效率，因為一旦數據超過H, 就沒必要往下走了。因為是往累加的方向進行，會更快逼近結果。
至此，剛好過去了24小時，把這題的運行時間 從 200.8s 優化到了 0.4s . 總結之：就是DFS遍歷應該以最優的方向進行遍歷，同時進行剪枝處理
想想真的有些感動，原來自己可以如此專注。
編程要對自己有信心。 昨天是個美麗的早晨，早早起來後就開始做網絡同步賽，結果一個早上，就因為這題，一直糾結著。昨晚洗澡的時候，心裡就想，都有好幾個人做出來了，我也一定能夠做出來，睡覺的時候，也在想著，明早起來再試試，肯定可以搞出來。
上午搞不定，下午繼續搞，下午搞不定，晚上繼續搞，晚上搞不定，明天接著搞~~~ WA 不息，Coding 不止。
最後附上測試數據和源碼
40 256
2 3 4 5 7 9 10 11 12 13 2 3 4 5 7 9 10 11 12 13 2 3 4 5 7 9 10 11 12 13 2 3 4 5 7 9 10 11 12 13
源碼：
1 // 給定一個集合，挑選一些數字，驗證能否組成 H
2
3 #include <iostream>
4 #include <cstdio>
5 #include <algorithm>
6
7 using namespace std;
8
9 int arr[50] = {0}; // 輸入的數組
10
11 bool isFound = false;
12
13 void func(const int n, const int H, int &sum, int step)
14 {
15 if (isFound)
16 {
17 return;
18 }
19
20 if (n > step && step >= 0 && sum < H)
21 {
22 // 先取當前這個數進行累加
23 sum += arr[step];
24
25 if (sum == H)
26 {
27 isFound = true;
28 return;
29 }
30 else if (sum < H)
31 {
32 func(n, H, sum, step+1);
33 }
34
35 sum -= arr[step]; // back trace
36
37 // 不取當前數字
38 func(n, H, sum, step+1);
39 }
40 else
41 {
42 // 結束一次選擇
43 //cout<<sum<<endl;
44 if (sum == H)
45 {
46 isFound = true;
47 }
48 }
49
50 }
51
52 // 降序處理
53 bool cmp(const int a, const int b)
54 {
55 return a > b;
56 }
57
58 int main(void)
59 {
60 freopen("in.txt","r", stdin);
61
62 int n = 0;
63 int H = 0;
64 unsigned long long sum = 0;
65
66 while( scanf("%d %d", &n, &H) != EOF )
67 {
68 for(int i=0; i<n; ++i)
69 {
70 scanf("%d", &arr[i]);
71 sum += arr[i];
72 }
73
74 if (sum < H)
75 {
76 printf("No\n"); //這是絕對不可能的。
77 continue;
78 }
79 else if (sum == H) // 剛剛好全選
80 {
81 printf("Yes\n");
82 continue;
83 }
84 // else sum > H // 進行遍歷
85
86 // 進行分解
87 int sum = 0;
88 int step = 0;
89 isFound = false;
90
91 sort(arr, arr+n, cmp); // 降序排序
92
93 func(n, H, sum, step);
94
95 if (isFound)
96 {
97 printf("Yes\n");
98 }
99 else
100 {
101 printf("No\n");
102 }
103
104 }
105
106 return 0;
107 }
