一個題目code的觀念解釋

題目如下:

Independent SET in a path

For a graph G = (V,E), asubSET U of V is an independent SET if there is no edge (v1,v2) forany v1 and v2 in U. Finding the maximum independent SET of a graph is animportant but very difficult problem. However, the problem can be easily solvedwhen the graph is special.

...

瀏覽完整內容，請先 註冊 或 登入會員

snowflying

如果用 dp + 遞迴 的話，大概長這樣，程式碼也不會太長

1. #include <cstdio>
   
2. #include <cstring>
   
3. #include <algorithm>
   
4. #define print printf
   
5. using namespace std;
   
6. 
   
7. int arr[512];
   
8. int dp[512];
   
9. 
   
10. int findMaxSum(int idx, int n)
    
11. {
    
12.     if(idx >= n)
    
13.         return 0;
    
14.         
    
15.     if(dp[idx] != -1)
    
16.         return dp[idx];
    
17.         
    
18.     return dp[idx] = max(arr[idx] + findMaxSum(idx+2, n), findMaxSum(idx+1, n));
    
19. }
    
20. 
    
21. int main()
    
22. {
    
23.     int n;
    
24.    
    
25.     while(scanf("%d", &n) == 1 && n != 0)
    
26.     {
    
27.         for(int i = 0 ; i < n ; ++i)
    
28.             scanf("%d", arr + i);
    
29.             
    
30.         memset(dp, 0xff, sizeof(dp));
    
31.         print("%d\n", findMaxSum(0, n));
    
32.     }
    
33. }

複製代碼

這可以寫迴圈版本，而且不需要用到陣列
原本的遞迴式相當於 dp[ i ] = max(arr[ i ] + dp[i + 2], dp[i + 1])   (邊界自行處理)
而由左往右處理，與由右往左處理，答案不會變
所以可以寫成 dp[ i ] = max(arr[ i ] + dp[i - 2], dp[i - 1])
也就是說，只要一直記錄前兩筆就行了

1. #include <cstdio>
   
2. #include <cstring>
   
3. #include <algorithm>
   
4. #define print printf
   
5. using namespace std;
   
6. 
   
7. int main()
   
8. {
   
9.     int n, arr[512], rec[2], tmp;
   
10.    
    
11.     while(scanf("%d", &n) == 1 && n != 0)
    
12.     {
    
13.         for(int i = 0 ; i < n ; ++i)
    
14.             scanf("%d", arr + i);
    
15.             
    
16.         if(n == 1)
    
17.         {
    
18.             print("%d\n", arr[0]);
    
19.             continue;
    
20.         }
    
21.         
    
22.         rec[0] = arr[0];
    
23.         rec[1] = max(arr[0], arr[1]);
    
24.         
    
25.         for(int i = 2 ; i < n ; ++i)
    
26.         {
    
27.             tmp = max(arr[i] + rec[0], rec[1]);
    
28.             rec[0] = rec[1];
    
29.             rec[1] = tmp;
    
30.         }
    
31.         print("%d\n", rec[1]);
    
32.     }
    
33.     return 0;
    
34. }

複製代碼

那份程式碼的概念也差不多是這樣

m1[ i ] 是 m3[i - 1]

m2[ i ] = m1[i - 1] + a[ i ];
所以 m2[ i ] 是 m3[i - 2] + a[ i ]

最後 m3[ i ] = max(m1[ i ], m2[ i ]);
即 m3[ i ] = max(m3[ i - 1],  m3[i - 2] + a[ i ])
跟上面的 dp[ i ] = max(arr[ i ] + dp[i - 2], dp[i - 1]) 一樣的意思
只是這並不需要開到 3 個陣列，而且跑的時候只需要前兩筆的資訊
所以開 3 個變數就行了

...

瀏覽完整內容，請先 註冊 或 登入會員

這題的解法概念大概是這樣
從第一個項目開始, 求出各項目的最大積分
直到求出最後一個項目為止
所以你要用迴圈還是遞迴, 老實說只看你自己偏好習慣

我們用 4 10 9 1 7 的例子來講
最前面的 4 只是長度, 略過不看
那我們先說  A[] = {10, 9, 1, 7} 是每個項目本身的分數
...

瀏覽完整內容，請先 註冊 或 登入會員

snowflying

inunu 發表於 2016-5-23 01:06 PM

下載: 訪客無法瀏覽下載點，請先 註冊 或 登入會員

這題的解法概念大概是這樣
從第一個項目開始, 求出各項目的最大積分
直到求出最後一個項目為止

S[1] = max(A[0], A[1]);
...

瀏覽完整內容，請先 註冊 或 登入會員

S[2] 本身並不是二選一的局面
我選擇了分開處理而不是進行檢查
這單純只是個人偏好

沒錯, 我昨天漏講了一個部份就是我的 S[k] 是 "包含了 k 項目" 的最大積分, 必需包含該項目
因此如你所說, 最後答案也必需有兩個選擇, 包含或不包含最後項目
也就是:
甲. S[n - 1]
...

瀏覽完整內容，請先 註冊 或 登入會員